Fewnomials are systems of polynomials with few monomials.
Khovanskii [Kh] showed that they have relatively few real solutions, independent of their number
of complex solutions, and it is a challenge to compute their real solutions without also computing complex solutions.
The improvement in Khovanskii's fewnomial bound by Bates, Bihan, and Sottile
[BBS,BiSo] leads to a new continuation
algorithm for computing the real solutions to a system of fewnomials.
This algorithm was described by Bates and Sottile [BaSo], who also provided a proof-of-concept
implementation in Maple.
The algorithm works by converting the fewnomial system into an equivalent Gale dual system, and then solving that
Work of Bates, Hauenstein, Niemerg, and Sottile [BHNS] describes algorithms and an
implementation for creating the dual Gale system given a fewnomial system, as well as methods to convert solutions
between the two equivalent systems.
Future projects will be concerned with tracking singular curves, and also a proper implementation of the
Web pages containing further details and software for each project.
Khovanskii-Rolle continuation for real solutions by
Dan Bates and
This web page describes the algorithm and includes maple scripts for our proof-of-concept implementation.
Matthew Niemerg, and
This page contains links to our software.
Daniel J. Bates, Jonathan Hauenstein, Matthew Niemerg, and F. Sottile,
Software for the Gale transform of
fewnomial systems and a Descartes rule for fewnomials, Almost Done.
Daniel J. Bates and F. Sottile,
Khovanskii-Rolle continuation for real
solutions, Foundations of
Computational Mathematics, Volume 11, Number 5 (2011), 563-587. DOI: 10.1007/s10208-011-9097-1. 25 pages.
Daniel J. Bates, Frédéric Bihan, and F. Sottile,
Bounds on the number of real solutions to
polynomial equations, IMRN, 2007, 2007:rnm114-7.
Frédéric Bihan and F. Sottile,
Gale duality for complete
intersection, Annales de l'Institut Fourier, Tome 58 (2008) fasicule 3, pp. 877--891.
Askold Khovanskii (translated by Smilka Zdavkovska),
Research supported by the National Science Foundation under grants DMS-0915211, DMS-1115668, DMS-1262428, DARPA YFA, and Sloan Research Fellowship.
Last modified: Mon May 18 20:56:01 CDT 2015