Extended F5 criteria
Extended F5 criteria
复制标题
DOI：
10.1016/j.jsc.2010.06.013
复制
发表时间：
2010-12
期刊：
影响因子：
--
通讯作者：
A. Hashemi;G. Ars
中科院分区：
文献类型：
--
作者：
A. Hashemi;G. Ars
T Faugère 的 F5 是计算 Gröbner 碱基最快的已知算法之一（参见 Faugère，2002）。该算法的效率来自两个标准，即 F5criteria，它为每个多项式分配一个签名。在本文中，我们研究了选择签名排序的重要性，并提出了一种新颖的签名排序。使用这种排序，我们扩展了 F5 标准，并基于这些扩展标准描述了像 F5 这样的新算法，该算法（尽管有 F5）不依赖于输入多项式的阶数。我们已经在 Magma 中实现了我们的算法，用于计算一般理想的 Gröbner 基，并通过一些示例评估其性能。我们证明新算法比 F5 更稳定、更高效，并且实验上它的停止度比 F5 更低。
T Faugère’s F5is one of the fastest known algorithm to compute Gröbner bases (see Faugère, 2002). The efficiency of this algorithm comes from two criteria namely F5criteria, for which it assigns to each polynomial a signature. In this paper, we study the importance of choosing an ordering on the signatures, and we propose a novel ordering on the signatures. Using this ordering, we extend the F5criteria, and we describe a new algorithm like F5based on these extended criteria which (despite of F5) does not depend on the order of input polynomials. We have implemented our algorithm in Magma for computing the Gröbner basis of a general ideal, and we evaluate its performance via some examples. We show that the new algorithm is more stable and more efficient than F5, and experimentally it stops at a lower degree than F5.