Wolfram Demonstrations Project

This Demonstration shows the main steps of Buchberger's Gröbner basis algorithm for a chosen monomial ordering. (Only two choices of monomial ordering are used here.) The input is a basis for an ideal in the ring of polynomials in two variables consisting of two polynomials, each of total degree two or less. The leading monomials of the polynomials are shown in red and the monomials themselves are shown next, arranged according to the chosen ordering.

With each step of the algorithm, the S-polynomials of the elements of the current bases are computed and their nonzero remainders with respect to the current basis are added to the basis until a Gröbner basis is obtained.

Contributed by: Andrzej Kozlowski

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.