10178

# The Buchberger Gröbner Basis Algorithm

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.

### 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.

### PERMANENT CITATION

 Share: Embed Interactive Demonstration New! Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

#### Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.