Skip to Main content Skip to Navigation
New interface
Conference papers

A polynomial-division-based algorithm for computing linear recurrence relations

Jérémy Berthomieu 1 Jean-Charles Faugère 1 
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
Abstract : Sparse polynomial interpolation, sparse linear system solving or modular rational reconstruction are fundamental problems in Computer Algebra. They come down to computing linear recurrence relations of a sequence with the Berlekamp–Massey algorithm. Likewise, sparse multivariate polynomial interpolation and multidi-mensional cyclic code decoding require guessing linear recurrence relations of a multivariate sequence. Several algorithms solve this problem. The so-called Berlekamp– Massey–Sakata algorithm (1988) uses polynomial additions and shifts by a monomial. The Scalar-FGLM algorithm (2015) relies on linear algebra operations on a multi-Hankel matrix, a multivariate generalization of a Hankel matrix. The Artinian Gorenstein border basis algorithm (2017) uses a Gram-Schmidt process. We propose a new algorithm for computing the Gröbner basis of the ideal of relations of a sequence based solely on multivariate polynomial arithmetic. This algorithm allows us to both revisit the Berlekamp–Massey–Sakata algorithm through the use of polynomial divisions and to completely revise the Scalar-FGLM algorithm without linear algebra operations. A key observation in the design of this algorithm is to work on the mirror of the truncated generating series allowing us to use polynomial arithmetic modulo a monomial ideal. It appears to have some similarities with Padé approximants of this mirror polynomial. Finally, we give a partial solution to the transformation of this algorithm into an adaptive one.
Document type :
Conference papers
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download
Contributor : Jérémy Berthomieu Connect in order to contact the contributor
Submitted on : Monday, May 7, 2018 - 5:07:42 PM
Last modification on : Thursday, June 23, 2022 - 10:11:44 AM
Long-term archiving on: : Monday, September 24, 2018 - 5:30:10 PM


main (2).pdf
Publisher files allowed on an open archive



Jérémy Berthomieu, Jean-Charles Faugère. A polynomial-division-based algorithm for computing linear recurrence relations. ISSAC 2018 - 43rd International Symposium on Symbolic and Algebraic Computation, Jul 2018, New York, United States. pp.79-86, ⟨10.1145/3208976.3209017⟩. ⟨hal-01784369⟩



Record views


Files downloads