Details:
Title  On the relation between the MXL family of algorithms and Gröbner basis algorithms  Author(s)  Martin R. Albrecht, Carlos Cid, JeanCharles Faugère, Ludovic Perret  Type  Article in Journal  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 recentlyproposed strategy, the socalled “Mutant strategy”, on which a new family of algorithms is based (MXL, MXL2 and MXL3). By studying and describing the algorithms based on Gröbner basis concepts, we demonstrate that the Mutant strategy can be understood to be equivalent to 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 Spolynomials considered in an iteration of the F 4 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 wellknown Gröbner basis equivalents. Using previous results that had shown the relation between the original XL algorithm and F 4 , we conclude that the MXL family of algorithms can be fundamentally reduced to redundant variants of F 4 .  Keywords  Gröbner bases, Polynomial system solving, Mutants  ISSN  07477171 
URL 
http://www.sciencedirect.com/science/article/pii/S074771711200003X 
Language  English  Journal  Journal of Symbolic Computation  Volume  47  Number  8  Pages  926  941  Year  2012  Edition  0  Translation 
No  Refereed 
No 
