Symbolic Computation Group

Let f = (f1,...,fn) be a system of n polynomial equations with unknowns X1,...,Xn. Can we approximate a solution of f in polynomial time? Progress in this classical problem has been recently made by the analysis of geometric and metric properties of the so called "solution variety"

V = {(f,z) : z is a solution of f}.

I will present an Average Las Vegas numerical procedure (joint work with L.M. Pardo) that solves this problem in average polynomial time. The procedure is based on M. Shub and S. Smale's homotopy method and its average running time is O(N^3), where N is the size of the input (i.e. the number of monomials of f).

I will also present some geometric properties of V that suggest the existence of faster algorithms (joint work with M. Shub), based on the study of the condition number and the associated metric in V.