A Faster Solution to Smale's 17th Problem I: Real Binomial Systems
share
Suppose F:=(f_1,…,f_n) is a system of random n-variate polynomials with f_i having degree ≤d_i and the coefficient of x^a_1_1⋯ x^a_n_n in f_i being an independent complex Gaussian of mean 0 and variance d_i!/a_1!⋯ a_n!(d_i-∑^n_j=1a_j )!. Recent progress on Smale's 17th Problem by Lairez — building upon seminal work of Shub, Beltran, Pardo, Bürgisser, and Cucker — has resulted in a deterministic algorithm that finds a single (complex) approximate root of F using just N^O(1) arithmetic operations on average, where N:=∑^n_i=1(n+d_i)!/n!d_i! (=n(n+max_i d_i)^O(min{n,max_i d_i)}) is the maximum possible total number of monomial terms for such an F. However, can one go faster when the number of terms is smaller, and we restrict to real coefficient and real roots? And can one still maintain average-case polynomial-time with more general probability measures? We show the answer is yes when F is instead a binomial system — a case whose numerical solution is a key step in polyhedral homotopy algorithms for solving arbitrary polynomial systems. We give a deterministic algorithm that finds a real approximate root (or correctly decides there are none) using just O(n^2(log(n)+logmax_i d_i)) arithmetic operations on average. Furthermore, our approach allows Gaussians with arbitrary variance. We also discuss briefly the obstructions to maintaining average-case time polynomial in nlogmax_i d_i when F has more terms.
READ FULL TEXT