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

Jérémy Berthomieu 1 Brice Boyer 1 Jean-Charles Faugère 1
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
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.
Type de document :
Communication dans un congrès
40th International Symposium on Symbolic and Algebraic Computation, Jul 2015, Bath, United Kingdom. pp.61--68, 2015, Proceedings of the 40th International Symposium on Symbolic and Algebraic Computation. 〈10.1145/2755996.2756673〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01237861
Contributeur : Jérémy Berthomieu <>
Soumis le : lundi 7 décembre 2015 - 16:53:57
Dernière modification le : lundi 29 mai 2017 - 14:23:06
Document(s) archivé(s) le : samedi 29 avril 2017 - 05:37:32

Fichier

BMS-HAL.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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, 2015, Proceedings of the 40th International Symposium on Symbolic and Algebraic Computation. 〈10.1145/2755996.2756673〉. 〈hal-01237861〉

Partager

Métriques

Consultations de
la notice

235

Téléchargements du document

87