Buchberger's algorithm: Difference between revisions

Revision as of 19:34, 25 November 2006

Revision as of 14:59, 22 February 2007

Line 17:

To date, all algorithms to compute Gröbner bases have been refinements of Buchberger's idea of computing ''S''-polynomials, then reducing them modulo ''F''.

The algorithm succeedsterminates 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. Therefore this algorithm does indeed stop. Unfortunately, it may take a very long time to terminate, corresponding to the fact that [[Gröbner bases]] can be ''extremely'' large.

Another method for computing Gröbner bases, based on the same mathematics as the Buchberger algorithm, is the [[Faugère F4 algorithm]].