Linear algebra for computing Gröbner bases of linear recursive multidimensional sequences. (November 2017)

• Record Type: Journal Article
• Authors: Berthomieu, Jérémy; Boyer, Brice; Faugère, Jean-Charles
• Is Part Of: Journal of symbolic computation. Volume 83(2017)
• Page Start: 36
• Page End: 67
• Publication Date: 2017-11
• Subjects: The BMS algorithm -- The FGLM algorithm -- Gröbner basis computation -- 0-dimensional ideal -- Multidimensional linear recursive sequence; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2016.11.005
• Languages: English
• ISSNs: 0747-7171

Abstract

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. ThisFGLM -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 theLEX 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.