On the complexity of the F5 Gröbner basis algorithm

Magali Bardet 1 Jean-Charles Faugère 2 Bruno Salvy 3
2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
3 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We study the complexity of Gr¨obner bases computation, in particular in the generic situation where the variables are in simultaneous Noether position with respect to the system. We give a bound on the number of polynomials of degree d in a Gr¨obner basis computed by Faug'ere's F5 algorithm (2002) in this generic case for the grevlex ordering (which is also a bound on the number of polynomials for a reduced Gr¨obner basis, independently of the algorithm used). Next, we analyse more precisely the structure of the polynomials in the Gr¨obner bases with signatures that F5 computes and use it to bound the complexity of the algorithm. Our estimates show that the version of F5 we analyse, which uses only standard Gaussian elimination techniques, outperforms row reduction of the Macaulay matrix with the best known algorithms for moderate degrees, and even for degrees up to the thousands if Strassen's multiplication is used. The degree being fixed, the factor of improvement grows exponentially with the number of variables.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2015, 70, pp.49--70. <10.1016/j.jsc.2014.09.025>
Liste complète des métadonnées

https://hal.inria.fr/hal-01064519
Contributeur : Jean-Charles Faugere <>
Soumis le : mardi 16 septembre 2014 - 14:48:23
Dernière modification le : dimanche 6 décembre 2015 - 01:05:36
Document(s) archivé(s) le : mercredi 17 décembre 2014 - 11:21:39

Fichier

analyseF5.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Magali Bardet, Jean-Charles Faugère, Bruno Salvy. On the complexity of the F5 Gröbner basis algorithm. Journal of Symbolic Computation, Elsevier, 2015, 70, pp.49--70. <10.1016/j.jsc.2014.09.025>. <hal-01064519>

Partager

Métriques

Consultations de
la notice

606

Téléchargements du document

390