Skip to Main content Skip to Navigation
Conference papers

A Gröbner-Basis Theory for Divide-and-Conquer Recurrences

Abstract : We introduce a variety of noncommutative polynomials that represent divide-and-conquer recurrence systems. Our setting involves at the same time variables that behave like words in purely noncom-mutative algebras and variables governed by commutation rules like in skew polynomial rings. We then develop a Gröbner-basis theory for left ideals of such polynomials. Strikingly, the nature of commutations generally prevents the leading monomial of a polynomial product to be the product of the leading monomials. To overcome the difficulty, we consider a specific monomial ordering, together with a restriction to monic divisors in intermediate steps. After obtaining an analogue of Buchberger's algorithm, we develop a variant of the 4 algorithm, whose speed we compare.
Document type :
Conference papers
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-02885579
Contributor : Frédéric Chyzak <>
Submitted on : Tuesday, June 30, 2020 - 6:41:27 PM
Last modification on : Monday, January 11, 2021 - 2:36:49 PM

File

gbdacr.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Frédéric Chyzak, Philippe Dumas. A Gröbner-Basis Theory for Divide-and-Conquer Recurrences. ISSAC - 2020 - 45th International Symposium on Symbolic and Algebraic Computation, Jul 2020, Kalamata, Greece. ⟨10.1145/3373207.3404055⟩. ⟨hal-02885579⟩

Share

Metrics

Record views

66

Files downloads

242