From: rojas@math.mit.edu (J. Maurice Rojas)
Newsgroups: sci.math.research
Subject: Real and complex root finding...
Date: 17 Apr 1997 21:45:00 -0400
J. Maurice Rojas
Applied Math Department
MIT
rojas@math.mit.edu
http://www-math.mit.edu/~rojas
April 17, 1997
Dear Colleagues,
In article 7528 of sci.math.research, Cassiano Durand (CD)
asked about solving systems of polynomial equations, especially
finding just the real (as opposed to complex) roots.
Here are a few answers...
-----------------------------------------
CD: (1) Is there any elimination method to get rid of the solutions at
CD: infinity?...
-----------------------------------------
The answer is yes. In fact, there are many such methods.
One method which has grown quite popular is to use Grobner
bases on the projective ideal generated by your system
in question to get rid of the roots at (projective) infinity. Another
method is to use the multivariate resultant and its recent (and
more efficient) extensions. Yet another alternative is to
use sparse homotopy techniques which avoid the paths at
(projective) infinity.
I know more about the two latter methods, so I'll restrict
my comments there. The upshot is that if you change your notion
of ``roots at infinity'' then you can get *MUCH* more efficient
algorithms. The proper setting for this yoga is the theory of
toric varieties, but the computational details can be outlined
in a more elementary way: Bezout's theorem and classical homotopy
methods typically overcount the number of roots of a polynomial system, and
there are more recent *convex geometric* methods which (almost completely)
avoid roots at infinity. This reduces the problem of finding
a good upper bound on the number of complex roots to the computation
of volumes of polyhedra.
The use of convex geometry for root counting seems
quite surprising, but begins to make a lot of sense after
you think about it a bit. This approach is due to Bernshtein,
Khovanskii, and Kushnirenko (BKK), around the mid-1970's. (There is
also an amazing paper by F. Minding from 1841 for the case
of two by two systems.) Their papers (except for Minding's) appear
in the journal
Functional Analysis and its Applications
beginning in 1976. The precise references are listed in
some papers of mine on the same topic, which extend BKK
in various ways. For instance, before 1994, there was no published
write-up of how to count solutions (convex geometrically) with some
coordinate zero. (The previous literature made this restriction for certain
technical reasons.) My papers can be found on my web-page, which is listed
above. There are also important papers by
Xiaoshen Wang and T.Y. Li
and
Birk Huber and Bernd Sturmfels
on root counting, which are also included in my references.
The last pair of pairs of authors have also written extensively
on sparse homotopy techniques which follows the ``right''
number of paths.
So you *can* quickly estimate the number of roots of a system
of equations, and need never bother with many roots at infinity.
There is also software for computing some of these root bounds.
Ioannis Emiris, Birk Huber, and Jan Verschelde all have implementations, most
of which are available on their web-pages. (There are links to their
pages from mine.) In particular, all of them have code for
computing *mixed volumes* (which are used in convex geometric
root counting), Emiris has code for sparse resultant-based solving,
and the last two researchers have code for sparse homotopy methods.
-------------------------------------------------------------------
CD: (2) Is there any way to isolate ONLY the real roots for the system?
-------------------------------------------------------------------
This is usually referred to as ``real-solving.'' Again,
Grobner bases pop up here, and there are some implementations of
Grobner-based algorithms for real-solving. Marie-Francoise Roy
is one of the leaders on the subject and her former student,
Fabrice Roullier, has worked extensively on implementing some
of these algorithms. These implementations also form a
significant part of a *LARGE* European software project
called POSSO.
However, the resultant is beginning to creep in here
as well. A recent paper of mine
``A New Approach to Counting Nash Equilibria''
covers a sparse-resultant based algorithm for real root counting,
and is available on my web-page. There is also work of
Dinesh Manocha on using resultants to isolate certain
solutions (e.g., the real ones) of polynomial systems via
the (classical) multivariate resultant. His papers are
available on his web-page, for which there is also a link
on my web-page. It is interesting to note that he (with John Canny)
has been able to solve certain 7 by 7 systems (occuring in
robotics) within milliseconds.
---------------------------------------------------------------------
CD: (3) What are the advantages/disadvantages of (Multi)Resultants vs.
CD: Wu-Ritt? What one can do that the other can't?
---------------------------------------------------------------------
I'm not an expert on Wu-Ritt, but I've seen work of
Ashu Rege and John Canny showing resultants to work a *LOT* faster
on certain applications (specifically, geometric theorem proving).
You might want to check their web-pages for their papers, especially
the papers on their ``Toolkit for Computational Algebraic Geometry''
and the package called APU. (I may have messed up the first title
slightly.)
Also, Wu-Ritt typically comes down to using some kind
of Grobner basis-like algebraic manipulations, which are pretty
slow for certain systems. In fairness, *everything* is slow
sometimes, so it's always a good idea to try more than one
algorithm.
However, I should mention that the sparse resultant
is a definite improvement on the classical resultant. So
I would use the former over the latter if possible. (The
sparse resultant refines the classical resultant so that
it takes the monomial term structure of a polynomial system
into account. So at worst, sparse=classical, and you lose
nothing.)
This new kind of resultant is due to Gelfand, Kapranov,
and Zelevinsky. In fact, they have a book published by
Birkhauser
Discriminants, Resultants, and Multidimensional
Determinants
covering this and much more. It's a beautiful book, but may
be hard to swallow for a beginner. So for the beginner,
I would recommend the survey article
``Introduction to Resultants''
by Bernd Sturmfels. His papers ``Sparse Elimination Theory''
and ``On the Newton Polytope of the Resultant'' are also
*very* good to look at. You should also look at the
collection of papers written by Canny and Emiris on
the sparse resultant (available on Ioannis Emiris' web page).
Finally, I have two MSRI preprints (``Some New Applications
of Toric Geometry'' and ``Toric Generalized Characteristic
Polynomials'') which refine and extend sparse
resultant based solving to degenerate systems.
Hope this helps. If you have any trouble with the
web, let me know and I'll be happy to send you paper copies
(at least of my own stuff). If enough people are interested,
I'll post a bibliography.
Best Wishes,
Maurice