## FAST RELIABLE ALGORITHMS FOR POLYNOMIAL SYSTEM SOLVING

Even in 2002, many modern software packages for polynomial
system solving still suffer from poor speed vs. accuracy trade-offs.
This is due to a lack of a complete understanding of the degeneracies
which can occur in various algorithms.

``Solving Degenerate Sparse Polynomial Systems Faster'' (J.
Symb. Comput. , vol. 28 (special issue on elimination theory), no. 1/2, July
and August 1999, pp. 155-186.) presents an efficient new method to handle
degenerate polynomial systems. In particular, a combinatorial construction
(the toric GCP) is introduced which significantly
speeds up an earlier algebraic perturbation algorithm dating
back to Canny and Grigoriev.

``Toric Laminations, Sparse Generalized Characteristic Polynomials, and a
Refinement of Hilbert's Tenth Problem'' presents a first step toward
understanding other issues within the realm of resultant-based
algorithms. This paper presents the new technique of univariate
reduction within a toric variety. Applications include:

- A preliminary description of the toric GCP (described in greater
detail above).
- A single-exponential time algorithm for a refinement of Hilbert's Tenth
Problem.
- A sparse-resultant based method for computing certain multisymmetric
functions of the roots of a polynomial system.
- New identities for sparse resultants with specialized coefficients.

This paper appears in
Foundations of Computational Mathematics, selected papers of a
conference, held at IMPA in Rio de Janeiro, January 1997, Felipe Cucker
and Mike Shub (eds.), Springer-Verlag (1997). You can click
HERE for a DVI copy of an improved version.
The multisymmetric function aspect of the above work can
be used to give a very fast algorithm for counting the
number of real (or complex) roots of a multivariate system of equations.
In particular, one can obtain the best known complexity bounds
in many cases of interest. This is covered in
``Intrinsic Near Quadratic Complexity Bounds
for Real Multivariate Root Counting,'' which will soon
appear in the proceedings of the Sixth Annual European Symposium
on Algorithms, Lecture Notes on Computer Science, Springer-Verlag (1998).