A new incremental algorithm for computing Groebner bases
A new incremental algorithm for computing Groebner bases
复制标题
DOI：
10.1145/1837934.1837944
复制
发表时间：
2010-07
期刊：
影响因子：
--
通讯作者：
Shuhong Gao;Yinhua Guan;Frank Volny
中科院分区：
文献类型：
--
作者：
Shuhong Gao;Yinhua Guan;Frank Volny
本文提出了一种计算Gröbner基的新算法。我们的算法以与F5和F5C相同的方式递增。在一个典型的步骤中，给出一个理想i和任意多项式g的Gröbner基G，并且需要计算从i通过连接g得到的新理想的Gröbner基。设(i：G)表示i除以g的冒号理想。我们的算法同时计算和(i：G)的Gröbner基。在以往的算法中，归结为零的S多项式是无用的，实际上，F5试图尽量避免这样的归约。然而，在我们的算法中，这些“无用的”S多项式给出了(I：G)中的元素，并且有助于加速后续的计算。在一些基准测试实例上的计算机实验表明，我们的算法比F5和F5C有更高的效率(速度是F5和F5C的两到十倍)。
In this paper, we present a new algorithm for computing Gröbner bases. Our algorithm is incremental in the same fashion as F5 and F5C. At a typical step, one is given a Gröbner basis G for an ideal I and any polynomial g, and it is desired to compute a Gröbner basis for the new ideal , obtained from I by joining g. Let (I: g) denote the colon ideal of I divided by g. Our algorithm computes Gröbner bases for and (I: g) simultaneously. In previous algorithms, S-polynomials that reduce to zero are useless, in fact, F5 tries to avoid such reductions as much as possible. In our algorithm, however, these "useless" S-polynomials give elements in (I: g) and are useful in speeding up the subsequent computations. Computer experiments on some benchmark examples indicate that our algorithm is much more efficient (two to ten times faster) than F5 and F5C.