Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleA new incremental algorithm for computing Groebner bases
Author(s) Shuhong Gao, Yinhua Guan, Frank Volny
TypeArticle in Conference Proceedings
AbstractIn 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 <I, g>, 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 <I, g> 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.
KeywordsBuchberger's algorithm, F5 algorithm, Grobner basis, colon ideal
URL http://www.ces.clemson.edu/~fvolny/pub/ISSAC2010.pdf
JournalProceedings of the 2010 International Symposium on Symbolic and Algebraic Computation
SeriesISSAC '10
AddressNew York, NY, USA
Translation No
Refereed Yes
ConferencenameISSAC '10 International Symposium on Symbolic and Algebraic Computation