next up previous contents
Next: Recipe 4---the Shape Up: Recipes Previous: Recipe 2---existence of

Recipe 3---reduction to triangular form

This recipe uses the pure lexicographic order. It is a consequence of the fact that any power of outweighs any combination of the other variables, and so on recursively down to , that if the number of solutions is finite then the Gröbner basis with respect to the lexicographic ordering has a special form:

These equations are in triangular form. The last equation contains only . The next-to-the last contains only and . Each equation as we move up contains only one more variable. This lets us count the number of solutions of the system, and in principle allows us to compute them. We solve the univariate polynomial for , and then the next one for in terms of each value of we found, and so on up the list to .

In practice there are numerical difficulties. This approach is a generalization of the characteristic polynomial approach to finding eigenvalues, which we know to be unstable. It is a generalization of the Row Echelon Form, which we know can be sensitive to errors (if the matrix is ill-conditioned). It is a generalization of the Euclidean algorithm, which can also be unstable. We will see later (time permitting) a linear algebraic approach that offers some slightly better hope of numerical stability.

Robert Corless
Tue Mar 12 21:09:19 EST 1996