Content deleted Content added
No edit summary |
No edit summary |
||
Line 11:
4. Add all the nonzero resultants of step 3 to ''F'', and repeat steps 1-4 until nothing new is added.
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 if the leading terms of ''f<sub>i</sub>'' and ''f<sub>j</sub>'' share no variables in common, then ''S<sub>ij</sub>'' will ''always'' reduce to 0 (if we use only f<sub>i</sub> and f<sub>j</sub> for reduction), so we needn't calculate it at all.
We are 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.
| |||