Khovanskii-Rolle Continuation:
Software for computing real solutions to fewnomials using Khovanskii-Rolle continuation

Dan Bates, Jonathan Hauenstein, Matthew Niemerg, and Frank Sottile

    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 Gale system. 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 algorithm.

Web pages containing further details and software for each project.

  • Khovanskii-Rolle continuation for real solutions by Dan Bates and Frank Sottile. This web page describes the algorithm and includes maple scripts for our proof-of-concept implementation.
  • galeDuality by Dan Bates, Jonathan Hauenstein, Matthew Niemerg, and Frank Sottile. This page contains links to our software.

  • Bibliography
    [BHNS] 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.

    [BaSo] 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.

    [BBS] 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.

    [BiSo] 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.

    [Kh] Askold Khovanskii (translated by Smilka Zdavkovska), Fewnomials, AMS, 1991.

    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