next up previous contents index
Next: 4.3.2 Homotopy (Continuation) Methods Up: 4.3 Classification of global Previous: 4.3 Classification of global   Contents   Index

4.3.1 Algebraic and Hybrid Techniques

Algebraic techniques for solving a nonlinear polynomial system are based on elimination theory. This theory deals with the problem of eliminating one or more variables from a system of polynomial equations, thus reducing the given problem to a problem of higher degree but in fewer variables. There are basically two fundamental approaches in elimination theory: (1) Resultants, and (2) Gröbner bases. Both of the above operate ideally in a symbolic algebra environment, and the coefficients of the polynomials involved are either rational or real algebraic numbers. There are several algorithms for solving nonlinear polynomial systems using the above approaches. All the algorithms are based on some fundamental algorithm that ``finds'' all the roots, real and complex, of a univariate polynomial. The word ``finds'' means, either the algorithm isolates the roots using intervals and rectangles, or encodes them as algebraic numbers, for further manipulation. Let $ f(x) $ be a polynomial with integer coefficients of degree $ m$ , $ d$ be a bound for the size of the coefficients of $ f(x) $ , and $ L(d)$ be the number of binary digits of $ d$ . Then, the (worst) running times of real root finding algorithms are functions of $ m$ , $ L(d)$ and are given in [64]. On the other hand, bisection methods for finding all roots of $ f$ , real and complex with similar running times, can be found in [442,357]. As it can be seen from the computing times found in [442,64,357], there is an enormous coefficient growth of all the quantities involved along the way (requiring significant computer memory). The latter is one of the most serious problems that all the algorithms using these techniques suffer from.

Resultant type algorithms: A resultant is a function of the coefficients of a given system of polynomials and when it is zero it provides an algebraic criterion for determining when this polynomial system has a solution. Resultants can be classified as classical, like the Sylvester, Bezout, Macaulay and $ u$ resultants, and non-classical like the sparse resultants. A good introduction to resultants and applications can be found in [89,409,413,310,381].

Algorithms based on resultant computation have been presented in [48,258,187,414,49]. They work well on systems with a small number of solutions $ M$ . However, on systems with large $ M$ , these algorithms suffer from efficiency problems. The main reason for that is that finding roots of high degree univariate polynomials can be a very slow procedure, as discussed above, due to the use of exact arithmetic.

Gröbner bases type algorithms: The theory of Gröbner bases was developed by Buchberger [46]. Gröbner bases are very special and useful bases (generator sets) for a special class of subsets of polynomial rings in $ l$ variables, called polynomial ideals. They are named after Gröbner who was Buchberger's thesis advisor. Gröbner bases can be thought of as a generalization of Euclid's algorithm for computing the greatest common divisor of two polynomials and of the Gauss triangularization algorithm for linear systems.

The usefulness of Gröbner basis for solving nonlinear polynomial systems comes from the fact that, whenever the system has a finite number of solutions, Gröbner basis provides an equivalent system of triangular form. Algorithms using Gröbner bases use the above fact, and appear in [47,218,228,115,445]. Using Gröbner bases, polynomial systems are converted to polynomial triangular systems, which can be solved by backward substitution, much in the manner of the Gauss triangularization algorithm for linear systems.

If the system has a finite number of solutions in the affine plane, as well as in the projective plane, then a Gröbner basis can be computed in $ O(m^l)$ time, where $ m$ is the highest degree among the polynomials and $ l$ is the number of variables. In case, however, that the system is not zero-dimensional at infinity, the time becomes $ O(m^{l^2})$ . These bounds do not take into account the coefficient growth. Gröbner basis algorithms work well on systems with few roots. This is one reason they have been considered seriously as a practical equation-solving tool. But when their complexity is measured as a function of the number of solutions, their performance is poor. As reported in [259], these algorithms frequently exhaust memory and computer resources even for low number of equations $ n$ and variables $ l$ (e.g. $ n, l \leq 5$ ) and moderate degrees $ m$ . To overcome this difficulty, algorithms that combine resultant and linear algebra techniques are more promising concerning efficiency [15,288,260,259]. These algorithms are generally hybrid and are based on algebraic and numerical analysis methods. In particular, this approach based on resultants transforms the problem into a sequence of eigenvalue problems. This method has found extensive application in various types of intersection problems [212].

next up previous contents index
Next: 4.3.2 Homotopy (Continuation) Methods Up: 4.3 Classification of global Previous: 4.3 Classification of global   Contents   Index
December 2009