A Faster Solution to Smale's 17th Problem I: Real Binomial Systems
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
2019 Copyright held by the owner/author(s). Publication rights Suppose F:= (f1, . . ., fn) is a system of random n-variate polynomials with fi having degree di and the coefficient of xa11 xann in fi being an independent complex Gaussian of di! mean 0 and variance a1!an!(diPnj=1 aj)!. Recent progress on Smale's 17th Problem by Lairez - building upon seminal work of Shub, Smale, Beltrn, Pardo, Brgisser, and Cucker - has resulted in a deterministic algorithm that finds a single (complex) approximate root of F using just NO(1) arithmetic operations on average, where N:= Pni=1 (n+di)! n!di! (= n(n + maxi di)O(min{n,maxi di)}) 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 that 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(n3 log2(n maxi di)) 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 n log maxi di when F has more terms.
