The Gröbner basis algorithm is one of the foundation stones of modern computer algebra. Given a set of multivariate polynomials and a specified monomial ordering, it produces a "nice" basis for the ideal (in the ring of polynomials in the given variables) generated by the input polynomials. Intuitively and somewhat simplifying, you can think of this as replacing the given set of polynomials by another set with the same solutions but with more desirable properties. For example, if the set of polynomials has a finite number of solutions and we use the lexicographic ordering, then the Gröbner basis will contain a univariate polynomial in one of the variables, which can be solved using standard univariate polynomial solving techniques. The other coordinates of the solution set can then be obtained from any of the remaining polynomials in the basis.

The basic Buchberger algorithm works as follows. For each pair of polynomials

,

in the already given basis

, a so-called S-polynomial is computed, given by the formula

where

denotes the leading term (also called head term) of a polynomial

with respect to the given monomial order, and

denotes the least common multiple of monomials

and

.

Compared with the basic Buchberger algorithm, ours contains one improvement: we make use of the so-called "disjoint leading terms" criterion, which says that if two polynomials in

have disjoint leading terms, then the polynomials are S-reduced to 0, so we do not need to compute them. This improves performance and saves display space. Finally, we note that the Gröbner basis computed here is not minimal or unique and does not coincide with the one returned by

*Mathematica*. There is a simple reduction procedure that will turn a Gröbner basis returned by the algorithm demonstrated here into the unique (for the given monomial order) reduced Gröbner basis that

*Mathematica* returns. The details can be found in any text on algorithmic algebra, including this one:

T. Becker and V. Weispfenning,

*Gröbner Bases*, New York: Springer-Verlag, 1993.