Complexity of computing zeros of structured polynomial systems

Abstract: Can we solve polynomial systems in polynomial time? This question received different answers in different contexts. The NP-completeness of deciding the feasibility of a general polynomial system in both Turing and BSS models of computation is certainly an important difficulty but it does not preclude efficient algorithms for computing all the roots of a polynomial system or solving polynomial systems with as many equations as variables, for which the feasibility over algebraically closed fields is granted under genericity hypotheses. And indeed, there are several ways of computing all $\delta^n$ zeros of a generic polynomial system of $n$ equations of degree $\delta > 1$ in $n$ variables with $\operatorname{poly}(\delta^n)$ arithmetic operations.

Smale's 17th problem is a clear-cut formulation of the problem in a numerical setting. It asks for an algorithm, with polynomial average complexity, for computing one approximate zero of a given polynomial system, where the complexity is to be measured with respect to the dense input size $N$, that is, the number of possible monomials in the input system.

We design a probabilistic algorithm that, on input $\epsilon>0$ and a polynomial system $F$ given by black-box evaluation functions, outputs an approximate zero of $F$, in the sense of Smale, with probability at least $(1-\epsilon)$. When applying this algorithm to $u \cdot F$, where $u$ is uniformly random in the product of unitary groups, the algorithm performs $\operatorname{poly}(n, \delta) \cdot L(F) \cdot \left( \Gamma(F) \log \Gamma(F) + \log \log \epsilon^{-1} \right)$ operations on average. Here $n$ is the number of variables, $\delta$ the maximum degree, $L(F)$ denotes the evaluation cost of $F$, and $\Gamma(F)$ reflects an aspect of the numerical condition of $F$. Moreover, we prove that for inputs given by random Gaussian algebraic branching programs of size $\operatorname{poly}(n,\delta)$, the algorithm runs on average in time polynomial in $n$ and $\delta$. Our result may be interpreted as an affirmative answer to a refined version of Smale's 17th problem, concerned with systems of structured polynomial equations.

This is joint work with Felipe Cucker and Pierre Lairez. The talk will not go into technical details and will be accessible to the general audience.

computational complexitynumerical analysis

Audience: researchers in the discipline

( paper | slides )

---

LA Combinatorics and Complexity Seminar

Series comments: Password is on the seminar page. www.math.ucla.edu/~pak/seminars/CCSem-Fall-2020.htm

---