Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems

How many operations do we need on the average to compute an approximate root of a random Gaussian polynomial system? Beyond Smale's 17th problem that asked whether a polynomial bound is possible, we prove a quasi-optimal bound (input size)(Formula presented). This improves upon the previously known (input size) (Formula presented) bound. The new algorithm relies on numerical continuation along \emph{rigid continuation paths}. The central idea is to consider rigid motions of the equations rather than line segments in the linear space of all polynomial systems. This leads to a better average condition number and allows for bigger steps. We show that on the average, we can compute one approximate root of a random Gaussian polynomial system of~n equations of degree at most D in n+1 homogeneous variables with O(n⁵D²)continuation steps. This is a decisive improvement over previous bounds that prove no better than (Formula presented) continuation steps on the average.