Buchberger's algorithm: Difference between revisions

Revision as of 17:12, 16 April 2012

Revision as of 19:25, 30 June 2012

Line 13:

The polynomial ''S''_''ij'' is commonly referred to as the ''S''-polynomial, where ''S'' refers to ''subtraction'' (Buchberger) or ''[[Syzygy (mathematics)|Syzygy]]'' (others). The pair of polynomials with which it is associated is commonly referred to as [[critical pair (logic)|critical pair]].

There are numerous ways to improve this algorithm beyond what has been stated above. For example, one could reduce all the new elements of ''F'' relative to each other before adding them. It also should be noted that ifIf the leading terms of ''f_i'' and ''f_j'' share no variables in common, then ''S_ij'' will ''always'' reduce to 0 (if we use only f_i and f_j for reduction), so we needn't calculate it at all.

The algorithm terminates because it is consistently increasing the size of the monomial ideal generated by the leading terms of our set ''F'', and [[Dickson's lemma]] (or the [[Hilbert basis theorem]]) guarantees that any such ascending chain must eventually become constant. Unfortunately, it may take a very long time to terminate, corresponding to the fact that [[Gröbner bases]] can be ''extremely'' large. Thus, it has large storage requirements ([[space complexity]]). Also, the [[time complexity]] of the algorithm is doubly exponential in the input data, which implies that its worst-case behavior can be very slow.