9717

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.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

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.
    • 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 »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+