@article{BERTHOMIEU201736,
    Abstract = {The so-called Berlekamp--Massey--Sakata algorithm computes a Gr{\"o}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{\"o}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 FGLM-like algorithm allows us to compute the relations of the table by extracting a full rank submatrix of a 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 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 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.},
    Author = {Berthomieu, J{\'e}r{\'e}my and Boyer, Brice and Faug{\`e}re, Jean-Charles},
    File = {Linear Algebra for Computing Gröbner Bases of Linear Recursive Multidimensional Sequences - 1-s2.0-S0747717116301249-main - a - e.pdf},
    ISSN = {0747-7171},
    Journal = {Journal of Symbolic Computation},
    Keywords = {The algorithm, The algorithm, Gr{\"o}bner basis computation, 0-dimensional ideal, Multidimensional linear recursive sequence},
    Note = {Special issue on the conference ISSAC 2015: Symbolic computation and computer algebra},
    Pages = {36 - 67},
    Title = {Linear algebra for computing Gr{\"o}bner bases of linear recursive multidimensional sequences},
    URL = {http://www.sciencedirect.com/science/article/pii/S0747717116301249},
    Volume = {83},
    Year = {2017},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0747717116301249},
    bdsk-url-2 = {https://doi.org/10.1016/j.jsc.2016.11.005},
    date-added = {2020-09-14 15:25:56 +0200},
    date-modified = {2020-09-14 15:25:56 +0200},
    doi = {10.1016/j.jsc.2016.11.005}
}

@article{BERTHOMIEU201736, Abstract = {The so-called Berlekamp--Massey--Sakata algorithm computes a Gr{\"o}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{\"o}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 FGLM-like algorithm allows us to compute the relations of the table by extracting a full rank submatrix of a 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 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 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.}, Author = {Berthomieu, J{\'e}r{\'e}my and Boyer, Brice and Faug{`e}re, Jean-Charles}, File = {Linear Algebra for Computing Gröbner Bases of Linear Recursive Multidimensional Sequences - 1-s2.0-S0747717116301249-main - a - e.pdf}, ISSN = {0747-7171}, Journal = {Journal of Symbolic Computation}, Keywords = {The algorithm, The algorithm, Gr{\"o}bner basis computation, 0-dimensional ideal, Multidimensional linear recursive sequence}, Note = {Special issue on the conference ISSAC 2015: Symbolic computation and computer algebra}, Pages = {36 - 67}, Title = {Linear algebra for computing Gr{\"o}bner bases of linear recursive multidimensional sequences}, URL = {http://www.sciencedirect.com/science/article/pii/S0747717116301249}, Volume = {83}, Year = {2017}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0747717116301249}, bdsk-url-2 = {https://doi.org/10.1016/j.jsc.2016.11.005}, date-added = {2020-09-14 15:25:56 +0200}, date-modified = {2020-09-14 15:25:56 +0200}, doi = {10.1016/j.jsc.2016.11.005} }