A faster solution to Smale's 17th problem. I: Real binomial systems

DOI10.1145/3326229.3326267MaRDI QIDQ5121124zbMATH OpenOpenAlexWikidataFDO

Authors Grigoris Paouris, Kaitlyn Phillipson, J. Maurice Rojas

Publication date 10 September 2020

Published in Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.09739

zbMATH Keywords

approximate rootaverage-case complexityNewton iterationrandom polynomialreal rootsSmale's 17th problemsparse polynomial

Mathematics Subject Classification ID

Real algebraic sets (14P05) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Numerical computation of solutions to single equations (65H05) Symbolic computation and algebraic computation (68W30)

Abstract: Suppose $F:=(f_1,ldots,f_n)$ is a system of random $n$-variate polynomials with $f_i$ having degree $leq!d_i$ and the coefficient of $x_1^{a_1}cdots{x}_n^{a_n}$ in $f_i$ being an independent complex Gaussian of mean $0$ and variance $frac{d}_i!a_1!cdots{a}_n!left(d_i-su{m}_{j=1}^n{a}_{j}ight)!$. Recent progress on Smale's 17th Problem by Lairez --- building upon seminal work of Shub, Beltran, Pardo, B"{u}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!:=!su{m}_{i=1}^{n}frac(n+d_i)!n!d_i!$ ($=n(n+ma{x}_i{d}_i{)}^{O(minn,ma{x}_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)+logma{x}_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 $nlogma{x}_i{d}_i$ when $F$ has more terms.

Recommendations

• Solving polynomial equations in smoothed polynomial time and a near solution to Smale's 17th problem
• On Smale's 17th problem: a probabilistic positive solution
• Fast computation of zeros of polynomial systems with bounded degree under finite-precision
• Smale's 17th problem: average polynomial time to compute affine and projective solutions
• On a problem posed by Steve Smale

Cited in

(4)

• Fast computation of zeros of polynomial systems with bounded degree under finite-precision
• A polyhedral homotopy algorithm for real zeros
• Mixed volumes of networks with binomial steady-states
• On Smale's 17th problem: a probabilistic positive solution

This page was built for publication: A faster solution to Smale's 17th problem. I: Real binomial systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5121124)