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

Buchberger's algorithm for polynomially nonlinear equations

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: $x^2 + yz - 2 = 0$, $xz + y^2 - 3 = 0$, $xy + z^2 - 5 = 0$. Application of the method requires a ranking of monomials. One possible choice is the lexicographic ranking: $x^ay^bz^c \prec x^iy^jz^k$ iff the first nonzero entry of $(i-a,j-b,k-c)$ is positive. Thus $1$ $ \prec$ $z $ $ \prec$ $ z^2$ $ ... $ $ \prec$ $y$ $ \prec$ $ yz$ $ \prec yz^2 $ $ \prec$ $ ... $ 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 $z(x^2+yz-2)-x(xz+y^2-3)$ since $x^2z$ is the lowest common multiple of their leading monomials $x^2$ and $xz$. 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: $361 x - 88 z^7 + 872 z^5 - 2690z^3 + 2375 z = 0$, $361 y + 8 z^7 + 52 z^5 - 740 z^3 + 1425 z = 0$, $8 z^8 - 100 z^6 + 438 z^4 - 760 z^2 + 361 =0$. 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