On the relation between the MXL family of algorithms and Gröbner basis algorithms

Abstract : The computation of Gröbner bases remains one of the most powerful methods for tackling the Polynomial System Solving (PoSSo) problem. The most efficient known algorithms reduce the Gröbner basis computation to Gaussian eliminations on several matrices. However, several degrees of freedom are available to generate these matrices. It is well known that the particular strategies used can drastically affect the efficiency of the computations. In this work we investigate a recently-proposed strategy, the so-called "Mutant strategy", on which a new family of algorithms is based (MXL,obner basis MXL2 and MXL3 ). By studying and describing the algorithms based on Gröbner concepts, we demonstrate that the Mutant strategy can be understood to be equivalentto the classical Normal Selection strategy currently used in Gröbner basis algorithms. Furthermore, we show that the "partial enlargement" technique can be understood as a strategy for restricting the number of S-polynomials considered in an iteration of the F4 Gröbner basis algorithm, while the new termination criterion used in MXL3 does not lead to termination at a lower degree than the classical Gebauer-Möller installation of Buchberger's criteria. We claim that our results map all novel concepts from the MXL family of algorithms to their well-known Grö obner basis equivalents. Using previous results that had shown the relation between the original XL algorithm and F4 , we conclude that the MXL family of algorithms can be fundamentally reduced to redundant variants of F4 .
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2012, 47 (8), pp.926-941. 〈http://www.sciencedirect.com/science/article/pii/S074771711200003X〉. 〈10.1016/j.jsc.2012.01.002〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00776071
Contributeur : Ludovic Perret <>
Soumis le : mardi 15 janvier 2013 - 00:03:46
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : mardi 16 avril 2013 - 03:52:29

Fichier

MAYA2-UPMCINRIA-mutant_2.0.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Martin R. Albrecht, Carlos Cid, Jean-Charles Faugère, Ludovic Perret. On the relation between the MXL family of algorithms and Gröbner basis algorithms. Journal of Symbolic Computation, Elsevier, 2012, 47 (8), pp.926-941. 〈http://www.sciencedirect.com/science/article/pii/S074771711200003X〉. 〈10.1016/j.jsc.2012.01.002〉. 〈hal-00776071〉

Partager

Métriques

Consultations de la notice

220

Téléchargements de fichiers

176