A new incremental algorithm for computing Groebner bases
Shuhong Gao, Yinhua Guan, Frank Volny · 2010
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.