Certified Numerical Solutions of Systems of Polynomial Equations
Homotopy or path-following methods are among the most popular numerical solvers for systems of polynomial equations. The general idea of these methods is as follows: for a given input system f, we generate another system g (usually with the same number of unknowns and degrees) which has a known solution. Then, we define some path (in the vector space of systems) whose extremes are g and f, and some path-following strategy is used to follow the "solution path", in such a way that the known zero of g is continued to approximate some zero of f. There has been much progress in the understanding of these methods during the last two decades. For example, we know how to describe this processin total detail, in such a way that, assuming exact computations, the method is certified (i.e. the output is an "approximate zero" of f), and the average complexity is polynomial in the number of monomials (dense encoding). I will summarize some of the last results in this framework. Many of these results are due to M.Shub & S. Smale, or joint work with L.M. Pardo, M. Shub, A. Leykin, J.P. Dedieu and G. Malajovich. I will also discuss the non-deterministic components of the present algorithm, and a recent advance by P. Burguisser and F. Cucker which shows that the algorithm can be made deterministic if quasi-polynomial running time is accepted.