Content deleted Content added
m Category:Algebra |
corrected definition of S-polynomial; added name; reference to commutative algebra |
||
Line 1:
In computational [[algebraic geometry]] and computational [[commutative algebra]], '''Buchberger's algorithm''' is a method of transforming a given set of generators for a polynomial [[ring ideal|ideal]] into a [[Gröbner basis]] with respect to some [[monomial order]]. One can view it as a generalization of the [[Euclidean algorithm]] for univariate [[greatest common divisor|gcd]] computation and of [[Gaussian elimination]] for linear systems.
A crude version of this algorithm proceeds as follows:
Line 5:
1. Start with ''F'' = {''f''<sub>1</sub>, ''f''<sub>2</sub>, ..., ''f''<sub>''k''</sub>}, a set of generators for your ideal. Let ''g<sub>i</sub>'' be the leading term of ''f<sub>i</sub>'' with respect to the given ordering, and denote the [[greatest common divisor]] of ''g<sub>i</sub>'' and ''g<sub>j</sub>'' by ''a<sub>ij</sub>''.
2. Let ''S''<sub>''ij''</sub> = (''
3. Using the [[multivariate division algorithm]], reduce all the ''S<sub>ij</sub>'' relative to the set ''F''.
4. Add all the nonzero polynomials resulting from step 3 to ''F'', and repeat steps 1-4 until nothing new is added.
The polynomial ''S''<sub>''ij''</sub> is commonly referred to as the ''S''-polynomial, where ''S'' refers to ''subtraction'' (Buchberger) or ''[[syzygy]]'' (others).
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.
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''.
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.▼
▲
[[Category:Algebra]]
| |||