In computational algebraic geometry and computational commutative algebra, Buchberger's algorithm is a method of transforming a given set of generators for a polynomial 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 gcd computation and of Gaussian elimination for linear systems. Algebraic geometry is a branch of mathematics which, as the name suggests, combines abstract algebra, especially commutative algebra, with geometry. ... In abstract algebra, commutative algebra is the field of study of commutative rings, their ideals, modules and algebras. ... In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring which generalizes important properties of integers. ... In computer algebra and computational algebraic geometry, a Gröbner basis (named after Wolfgang Gröbner) is a particular kind of generating subset of an ideal I in a polynomial ring. ... In mathematics, a monomial order is a total order on the set of all monomials (considering monomials which only differ in their coefficient to be the same) satisfying two additional properties. ... The Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (gcd) of two integers. ... In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (GCF) or highest common factor (hcf) of two integers which are not both zero is the largest integer that divides both numbers. ... In mathematics, Gaussian elimination or Gauss-Jordan elimination, named after Carl Friedrich Gauss and Wilhelm Jordan, is an algorithm in linear algebra for determining the solutions of a system of linear equations, for determining the rank of a matrix, and for calculating the inverse of an invertible square matrix. ...

A crude version of this algorithm proceeds as follows:

1. Start with F = {f₁, f₂, ..., f_k}, a set of generators for your ideal. Let g_i be the leading term of f_i with respect to the given ordering, and denote the least common multiple of g_i and g_j by a_ij. In arithmetic and number theory the least common multiple or lowest common multiple (lcm) or smallest common multiple of two integers a and b is the smallest positive integer that is a multiple of both a and b. ...

2. Let S_ij = (a_ij / g_i) f_i − (a_ij / g_j) f_j. Note that the leading terms here will cancel by construction.

3. Using the multivariate division algorithm, reduce all the S_ij relative to the set F. Although polynomials in more than one variable do not form a Euclidean domain, so it is not possible to construct a true division algorithm, an approximate multivariate division algorithm can be constructed. ...

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_ij is commonly referred to as the S-polynomial, where S refers to subtraction (Buchberger) or syzygy (others). Syzygy can refer to any of several different things: Astronomy In astronomy, a syzygy (Greek: yoked together) is a situation where three bodies are situated along a straight line. ...

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_i and f_j share no variables in common, then S_ij will always reduce to 0 (if we use only f_i and f_j 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.

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. In mathematics, Dicksons lemma is a finiteness statement applying to n-tuples of natural numbers. ... In mathematics, Hilberts basis theorem, first proved by David Hilbert in 1888, states that, if k is a field, then every ideal in the ring of multivariate polynomials k[x1, x2, ..., xn] is finitely generated. ...