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