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
Journal articles

Linear Algebra for Computing Gröbner Bases of Linear Recursive Multidimensional Sequences

Jérémy Berthomieu 1 Brice Boyer 1 Jean-Charles Faugère 1
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
Abstract : The so-called Berlekamp~-- Massey~-- Sakata algorithm computes a Gröbner basis of a $0$-dimensional ideal of relations satisfied by an input table. It extends the Berlekamp~-- Massey algorithm to $n$-dimensional tables, for $n>1$. We investigate this problem and design several algorithms for computing such a Gröbner basis of an ideal of relations using linear algebra techniques. The first one performs a lot of table queries and is analogous to a change of variables on the ideal of relations. As each query to the table can be expensive, we design a second algorithm requiring fewer queries, in general. This \textsc{FGLM}-like algorithm allows us to compute the relations of the table by extracting a full rank submatrix of a \emph{multi-Hankel} matrix (a multivariate generalization of Hankel matrices). Under some additional assumptions, we make a third, adaptive, algorithm and reduce further the number of table queries. Then, we relate the number of queries of this third algorithm to the \emph{geometry} of the final staircase and we show that it is essentially linear in the size of the output when the staircase is convex. As a direct application to this, we decode $n$-cyclic codes, a generalization in dimension $n$ of Reed Solomon codes. We show that the multi-Hankel matrices are heavily structured when using the \textsc{LEX} ordering and that we can speed up the computations using fast algorithms for quasi-Hankel matrices. Finally, we design algorithms for computing the generating series of a linear recursive table.
Document type :
Journal articles
Complete list of metadata

Cited literature [32 references]  Display  Hide  Download

https://hal.inria.fr/hal-01253934
Contributor : Jérémy Berthomieu Connect in order to contact the contributor
Submitted on : Friday, November 18, 2016 - 5:39:30 PM
Last modification on : Friday, February 4, 2022 - 3:07:39 AM
Long-term archiving on: : Monday, March 20, 2017 - 4:43:29 PM

File

main.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Jérémy Berthomieu, Brice Boyer, Jean-Charles Faugère. Linear Algebra for Computing Gröbner Bases of Linear Recursive Multidimensional Sequences. Journal of Symbolic Computation, Elsevier, 2017, 83 (Supplement C), pp.36-67. ⟨10.1016/j.jsc.2016.11.005⟩. ⟨hal-01253934v3⟩

Share

Metrics

Record views

698

Files downloads

693