M4GB: An Efficient Gröbner-Basis Algorithm
M4GB: An Efficient Gröbner-Basis Algorithm
复制标题
M4GB：一种高效的 Gröbner 基础算法
DOI：
10.1145/3087604.3087638
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
M.M.J. Stevens
中科院分区：
文献类型：
--
作者：
R. Makarim;M.M.J. Stevens
本文介绍了一种新的计算Grobner基的高效算法--M4 GB。与福格尔的算法F4一样，它是Buchberger算法的扩展，它描述了：如何存储已经计算的(尾部)约简的基本多项式的倍数，以防止约简步骤中的冗余工作；以及如何利用有效的线性代数进行约简步骤。与F4相比，它消除了在处理可约单项式时的更多冗余工作。此外，我们的算法没有将许多关键对的约简转化为某个大矩阵的行约简，而是更自然地描述了该算法，并且在逐个处理关键对时是高效的。此功能意味着，通常情况下，M4 GB需要处理的关键对比F4少，并且减少了与F4观察到的一系列问题的规律性程度增加相关的时间和数据复杂性。为了实现高效率，M4 GB被专门设计成只对减尾多项式进行运算，即除前导项外的所有项都是不可约多项式。这使得它可以在项多项式乘法的计算中直接执行完全减法，其中所有计算都是对不可约单项式上的系数向量进行的。我们已经实现了为稠密超定义多项式系统量身定做的新算法的一个版本，作为概念证明，并公开了我们的源代码。我们已经将我们的实现与FGBlib、Magma和OpenF4在各种密集的福冈MQ挑战问题上的实现进行了比较，我们能够在合理的时间和内存内计算这些问题。我们观察到，对于这些MQ问题，在所有这些实现中，M4 GB使用的总CPU时间和内存最少，这通常是一个重要因素。在福冈MQ挑战赛中，类型V和类型VI的起始挑战有16个方程式，这些方程式是基于使用Magma外推一个多月的计算时间而选择的。M4 GB让我们为这些福冈MQ挑战创造了新的记录，打破了类型V(F28)最多18个方程式和类型VI(F31)最多19个方程式，每个方程式在我们的双至强系统上最多可以在11天内计算出来。
This paper introduces a new efficient algorithm for computing Grobner-bases named M4GB. Like Faugere's algorithm F4 it is an extension of Buchberger's algorithm that describes: how to store already computed (tail-)reduced multiples of basis polynomials to prevent redundant work in the reduction step; and how to exploit efficient linear algebra for the reduction step. In comparison to F4 it removes further redundant work in the processing of reducible monomials. Furthermore, instead of translating the reduction of many critical pairs into the row reduction of some large matrix, our algorithm is described more natively and is efficient while processing critical pairs one by one. This feature implies that typically M4GB has to process fewer critical pairs than F4, and reduces the time and data complexity 'staircase' related to the increasing degree of regularity for a sequence of problems one observes for F4. To achieve high efficiency, M4GB has been designed specifically to operate only on tail-reduced polynomials, i.e., polynomials of which all terms except the leading term are non-reducible. This allows it to perform full-reduction directly in the computation of a term polynomial multiplication, where all computations are done over coefficient vectors over the non-reducible monomials. We have implemented a version of our new algorithm tailored for dense overdefined polynomial systems as a proof of concept and made our source code publicly available. We have made a comparison of our implementation against the implementations of FGBlib, Magma and OpenF4 on various dense Fukuoka MQ challenge problems that we were able to compute in reasonable time and memory. We observed that M4GB uses the least total CPU time and the least memory of all these implementations for those MQ problems, often by a significant factor. In the Fukuoka MQ challenges, the starting challenges of Type V and Type VI have 16 equations which was chosen based on an extrapolated computational runtime of more than a month using Magma. M4GB allowed us to set new records for these Fukuoka MQ challenges breaking Type V (F28) up to 18 equations and Type VI (F31) up to 19 equations, each can be computed within up to 11 days on our dual Xeon system.