Buchberger's algorithm: Difference between revisions

Revision as of 14:27, 10 July 2006

Revision as of 19:43, 1 August 2006

Line 18:

The algorithm succeeds 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]].

==External links==