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.