A Faster Solution to Smale's 17th Problem I: Real Binomial Systems
Academic Article

 Overview

 Research

 Identity

 Additional Document Info

 View All

Overview
abstract

© 2019 Copyright held by the owner/author(s). Publication rights Suppose F:= (f1, . . ., fn) is a system of random nvariate 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!(di−Pnj=1 aj)!. Recent progress on Smale's 17th Problem by Lairez  building upon seminal work of Shub, Smale, Beltrán, Pardo, Bürgisser, 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 averagecase polynomialtime 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 averagecase time polynomial in n log maxi di when F has more terms.
author list (cited authors)

Paouris, G., Phillipson, K., & Rojas, J. M.
citation count
publication date
publisher
Research
keywords

Approximate Root

Averagecase Complexity

Newton Iteration

Random Polynomial

Real Roots

Smale's 17th Problem

Sparse Polynomial
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume