** Next:** Differential Algebra
** Up:** Background and Motivation
** Previous:** Background for Linear Systems

We briefly discuss Buchberger's algorithm, which has
led to a revolution in algorithmic methods and applications [8]
for nonlinear mathematics. Consider
the system of polynomial equations:
,
,
.
Application of the method requires a ranking of monomials.
One possible choice
is the lexicographic ranking:
iff the first nonzero entry of is positive.
Thus
etc.
Buchberger's algorithm proceeds by computing so-called S-polynomials
between pairs of polynomials. For example the S-polynomial of the first
two polynomials is
since
is the lowest common multiple of their leading monomials
and . The result is then reduced with respect to the
system. If all the S-polynomials vanish after reduction then the
algorithm has terminated with the system in the form of a Gröbner
Basis. Otherwise the nontrivial reduced S-polynomials are appended to
the system and the process is repeated.
The resulting Gröbner Basis (expressed as equations) for our example is:
,
,
.
The above triangularized form is convenient for predicting the existence
of, and for bounding the number of the system's solutions.
It is also convenient for numerically (or exactly) solving the system.
Such properties reflect valuable characteristics of Gröbner Bases in
general, although of course polynomials of degree greater than
four cannot always be solved exactly.
The Buchberger algorithm also gives a decision method for
the ideal membership problem [8,10].

** Next:** Differential Algebra
** Up:** Background and Motivation
** Previous:** Background for Linear Systems
Greg Reid
2003-11-24