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

Abstract

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 ${\text{(input size)}}^{1+o(1)}$. This improves upon the previously known ${\text{(input size)}}^{\frac{3}{2}+o(1)}$ 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^5{D}^2)$ continuation steps. This is a decisive improvement over previous bounds that prove no better than ${\sqrt{2}}^{\min (n,D)}$ continuation steps on the average.

References in corpus (2)

• The condition number of join decompositions
• A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time