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

详细信息	查看全文 | 推荐本文 |

• 作者：Martin R. Albrecht^a ; ^malb@lip6.fr ; ^{martinralbrecht@googlemail.com} ; Carlos Cid^b ; ^{carlos.cid@rhul.ac.uk} ; Jean-Charles Faug&egrave ; re^a ; ^{jean-charles.faugere@inria.fr} ; Ludovic Perret^a ; ^{ludovic.perret@lip6.fr}
• 关键词：Grö ; bner bases ; Polynomial system solving ; Mutants
• 刊名：Journal of Symbolic Computation
• 出版年：2012
• 期刊代码：140_07477171
• 类别：cp
• 出版时间：August, 2012
• 卷：47
• 期：8
• 页码：926-941
• 文件大小：304 K

摘要

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 鈥淢utant strategy鈥?/em>, on which a new family of algorithms is based (MXL, MXL₂ and MXL₃). 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 鈥減artial enlargement鈥?technique can be understood as a strategy for restricting the number of S-polynomials considered in an iteration of the Gr枚bner basis algorithm, while the new termination criterion used in MXL₃ does not lead to termination at a lower degree than the classical Gebauer-M枚ller installation of Buchberger鈥檚 criteria. We claim that our results map all novel concepts from the MXL family of algorithms to their well-known Gr枚bner basis equivalents. Using previous results that had shown the relation between the original XL algorithm and , we conclude that the MXL family of algorithms can be fundamentally reduced to redundant variants of .