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

(1) , (1) , (1)
1
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.
Fichier principal
Vignette du fichier
BMS-HAL.pdf (233.36 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

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⟩
170 View
346 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More