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

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.
Keywords :
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2017, 83 (Supplement C), pp.36-67. 〈10.1016/j.jsc.2016.11.005〉
Domaine :

Littérature citée [32 références]

https://hal.inria.fr/hal-01253934
Contributeur : Jérémy Berthomieu <>
Soumis le : vendredi 18 novembre 2016 - 17:39:30
Dernière modification le : vendredi 31 août 2018 - 09:25:58
Document(s) archivé(s) le : lundi 20 mars 2017 - 16:43:29

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

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〉

Métriques

Consultations de la notice

410

Téléchargements de fichiers