On Smale's 17th problem over the reals

2024/05/02 by Montanari, Andrea, Subag, Eliran
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Probability (math.PR)

paper · doi:10.48550/arxiv.2405.01735

Abstract

We consider the problem of efficiently solving a system of n non-linear equations in \mathbb R^d. Addressing Smale's 17th problem stated in 1998, we consider a setting whereby the n equations are random homogeneous polynomials of arbitrary degrees. In the complex case and for n= d-1, Beltrán and Pardo proved the existence of an efficient randomized algorithm and Lairez recently showed it can be de-randomized to produce a deterministic efficient algorithm. Here we consider the real setting, to which previously developed methods do not apply. We describe a polynomial time algorithm that finds solutions (with high probability) for n= d -O(√(dlog d)) if the maximal degree is bounded by d² and for n=d-1 if the maximal degree is larger than d².

Related

• Semi-regular sequences and other random systems of equations
• A Faster Solution to Smale's 17th Problem I: Real Binomial Systems
• A Randomized Parallel Algorithm with Run Time O(n²) for Solving an n × n System of Linear Equations
• Smale's Fundamental Theorem of Algebra reconsidered
• Condition length and complexity for the solution of polynomial systems