|
|
|
|
|
Buchberger's AlgorithmIn computational algebraic geometry, Buchberger's algorithm is a method of transforming a given set of generators for a polynomial ideal into a Grbner basis with respect to some monomial order. A crude version of this algorithm proceeds as follows: 1. Start with F = {f1, f2, ..., fk}, a set of generators for your ideal. Let gi be the leading term of fi with respect to the given ordering, and denote the greatest common divisor of gi and gj by aij. 2. Let Sij = (gj /aij) fi − (gi /aij) fj. Note that the leading terms here will cancel by construction. 3. Using the multivariate division algorithm, reduce all the Sij 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. 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 fi and fj share no variables in common, then Sij will always reduce to 0 (if we use only fi and fj 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 Grbner bases can be extremely large.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|