HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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

Contributor : Frédéric Chyzak Connect in order to contact the contributor
Submitted on : Tuesday, June 30, 2020 - 6:41:27 PM
Last modification on : Friday, May 20, 2022 - 12:52:02 PM


Files produced by the author(s)



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⟩



Record views


Files downloads