Linear Algebra for Computing Gröbner Bases of Linear Recursive Multidimensional Sequences - Archive ouverte HAL Access content directly
Conference Papers Year : 2015

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

Jérémy Berthomieu
Brice Boyer
• Function : Author
• PersonId : 973546
Jean-Charles Faugère

#### Abstract

Sakata generalized the Berlekamp -- Massey algorithm to $n$ dimensions in~1988. The Berlekamp -- Massey -- Sakata (BMS) algorithm can be used for finding a Gröbner basis of a $0$-dimensional ideal of relations verified by a table. We investigate this problem using linear algebra techniques, with motivations such as accelerating change of basis algorithms (FGLM) or improving their complexity. We first define and characterize multidimensional linear recursive sequences for $0$-dimensional ideals. Under genericity assumptions, we propose a randomized preprocessing of the table that corresponds to performing a linear change of coordinates on the polynomials associated with the linear recurrences. This technique then essentially reduces our problem to using the efficient $1$-dimensional Berlekamp -- Massey (BM) algorithm. However, the number of probes to the table in this scheme may be elevated. We thus consider the table in the \emph{black-box} model: we assume probing the table is expensive and we minimize the number of probes to the table in our complexity model. We produce an FGLM-like algorithm for finding the relations in the table, which lets us use linear algebra techniques. Under some additional assumptions, we make this algorithm adaptive and reduce further the number of table probes. This number can be estimated by counting the number of distinct elements in a multi-Hankel matrix (a multivariate generalization of Hankel matrices); we can relate this quantity with the \emph{geometry} of the final staircase. Hence, in favorable cases such as convex ones, the complexity is essentially linear in the size of the output. Finally, when using the \textsc{lex} ordering, we can make use of fast structured linear algebra similarly to the Hankel interpretation of Berlekamp -- Massey.

#### Domains

Computer Science [cs] Symbolic Computation [cs.SC]

### Dates and versions

hal-01237861 , version 1 (07-12-2015)

### Identifiers

• HAL Id : hal-01237861 , version 1
• DOI :

### Cite

Jérémy Berthomieu, Brice Boyer, Jean-Charles Faugère. Linear Algebra for Computing Gröbner Bases of Linear Recursive Multidimensional Sequences. 40th International Symposium on Symbolic and Algebraic Computation, Jul 2015, Bath, United Kingdom. pp.61--68, ⟨10.1145/2755996.2756673⟩. ⟨hal-01237861⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

170 View