Buchberger's algorithm

In the theory of multivariate polynomials, Buchberger's algorithm is a method for transforming a given set of polynomials into a Gröbner basis, which is another set of polynomials that have the same common zeros and are more convenient for extracting information on these common zeros. It was introduced by Bruno Buchberger simultaneously with the definition of Gröbner bases. Euclidean algorithm for polynomial greatest common divisor computation and Gaussian elimination of linear systems are special cases of Buchberger's algorithm when the number of variables or the degrees of the polynomials are respectively equal to one. For other Gröbner basis algorithms, see . A crude version of this algorithm to find a basis for an ideal I of a polynomial ring R proceeds as follows: Input A set of polynomials F that generates I Output A Gröbner basis G for I G := F For every fi, fj in G, denote by gi the leading term of fi with respect to the given monomial ordering, and by aij the least common multiple of gi and gj. Choose two polynomials in G and let Sij = aij / g f − aij / gj fj (Note that the leading terms here will cancel by construction). Reduce Sij, with the multivariate division algorithm relative to the set G until the result is not further reducible. If the result is non-zero, add it to G. Repeat steps 2-4 until all possible pairs are considered, including those involving the new polynomials added in step 4. Output G The polynomial Sij is commonly referred to as the S-polynomial, where S refers to subtraction (Buchberger) or syzygy (others). The pair of polynomials with which it is associated is commonly referred to as critical pair. 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. 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.