F5C: A variant of Faugère's F5 algorithm with reduced Gröbner bases
F5C: A variant of Faugère's F5 algorithm with reduced Gröbner bases
复制标题
DOI：
10.1016/j.jsc.2010.06.019
复制
发表时间：
2009-06
期刊：
影响因子：
--
通讯作者：
C. Eder;J. Perry
中科院分区：
文献类型：
--
作者：
C. Eder;J. Perry
用于计算 Gröbner 基的 F5 算法通过仔细分析分配给每个计算多项式的签名实现了高效率。然而，它计算和使用许多多项式，结果证明这些多项式是多余的。消除这些冗余多项式是一项艰巨的任务，因为它们对应于减少所需的签名。本文重新审视了 F5 的基础理论并描述了 F5C，这是一种新的变体，可以修剪冗余多项式，然后重新计算签名以保持正确性。该策略成功地减少了开销和执行时间。
The F5 algorithm for computing Gröbner bases achieves a high level of efficiency through the careful analysis of signatures assigned to each computed polynomial. However, it computes and uses many polynomials that turn out to be redundant. Eliminating these redundant polynomials is a non-trivial task, because they correspond to signatures required for reduction. This paper revisits the theory underlying F5 and describes F5C, a new variant that prunes redundant polynomials, then re-computes signatures to preserve correctness. This strategy successfully reduces both overhead and execution time.