Algebraic Geometry Seminar
Frank Sottile
Texas AM
Khovanskii-Rolle continuation for real solutions
Abstract: Current continuation methods for finding all solutions to systems of
polynomial equations first compute all complex solutions, and then sieve
them to find the real solutions. This method is not optimal in that
number of paths to be followed may not reflect the actual number of real
solutions. This problem is particularly acute for fewnomial systems, a
class of systems whose number of real solutions is typically much
smaller than their number of complex solutions.
Recent work has established a new bound for the number of real
solutions to a system of fewnomials, by transforming the system of
polynomials into an equivalent system of master functions on a
hyperplane complement, called the gale dual system. Sturmfels observed
that the method used to establish those bounds, the Khovanskii-Rolle
Theorem, could be the basis of a continuation algorithm to compute all
real solutions, which has the additional feature that the path
continuation only follows real solutions.
In this talk, I will sketch the main ideas in this new algorithm.
This will also include a sketch of the proof of these new fewnomial
bounds, and some of the continuation issues which arisen in an
implementation of the algorithm. We remark that the complexity of this
algorithm depends on the ambient (real dimension) and the fewnomial
bound, and not on the number of complex solutions. The implementation of
the algorithm is joint work with Daniel J. Bates, while the fewnomial
bounds and reduction to Gale systems is work with Frédéric Bihan and Bates.
Thursday October 25, 2007 at 4:00 PM in SEO 636