Details

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.