Linear Algebra for Computing Gröbner Bases of Linear Recursive Multidimensional SequencesReport as inadecuate




Linear Algebra for Computing Gröbner Bases of Linear Recursive Multidimensional Sequences - Download this document for free, or read online. Document in PDF available to download.

1 PolSys - Polynomial Systems LIP6 - Laboratoire d-Informatique de Paris 6, Inria de Paris

Abstract : The so-called Berlekamp~- Massey~- Sakata algorithmcomputes a Gröbner basis of a $0$-dimensional ideal of relations satisfied by an inputtable. It extends the Berlekamp~- Massey algorithmto $n$-dimensional tables, for $n>1$.We investigate this problem and design several algorithms forcomputing such a Gröbner basis of an ideal of relations using linearalgebra techniques.The first one performs a lot of table queries andis analogous to a change of variables on the ideal of relations.As each query to the table can be expensive,we design a second algorithmrequiring fewer queries, in general.This \textsc{FGLM}-like algorithm allows us to compute the relations of thetable by extracting a full rank submatrix of a \emph{multi-Hankel}matrix a multivariate generalization of Hankel matrices.Under someadditional assumptions, we make a third, adaptive, algorithm and reducefurther the number of table queries.Then, we relate the number of queries ofthis third algorithm to the\emph{geometry} of the final staircase and we show that it isessentially linear in the size of the output when the staircase is convex.As a direct application to this, we decode $n$-cyclic codes, ageneralization in dimension $n$ of Reed Solomon codes. We show that the multi-Hankelmatrices are heavily structured when using the \textsc{LEX} orderingand that we can speed up the computations using fast algorithms forquasi-Hankel matrices.Finally, we designalgorithms for computing the generating series of a linear recursivetable.

Keywords : Gröbner basis computation FGLM algorithm $0$-dimensional ideal Berlekamp - Massey - Sakata algorithm multidimensional linear recurrent sequence





Author: Jérémy Berthomieu - Brice Boyer - Jean-Charles Faugère -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents