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:

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).