Smale’s 17th problem: Average polynomial time to compute affine and projective solutions

DOI10.1090/S0894-0347-08-00630-9zbMath1206.90173WikidataQ56697970 ScholiaQ56697970MaRDI QIDQ3079201

Luis Miguel Pardo, Carlos Beltran

Publication date: 2 March 2011

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

approximate zerohomotopy methodscomplexity of methods in algebraic geometry

Mathematics Subject Classification ID

Nonlinear programming (90C30) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Related Items

Random sampling in computational algebra: Helly numbers and violator spaces, The Legacy of Turing in Numerical Analysis, Random monomial ideals, Functional norms, condition numbers and numerical algorithms in algebraic geometry, On the zeta Mahler measure function of the Jacobian determinant, condition numbers and the height of the generic discriminant, On the geometry and topology of the solution variety for polynomial system solving, A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time, Smale's fundamental theorem of algebra reconsidered, Complexity of path-following methods for the eigenvalue problem, A continuation method to solve polynomial systems and its complexity, Rigid continuation paths II. structured polynomial systems, Learning a performance metric of Buchberger's algorithm, Fast linear homotopy to find approximate zeros of polynomial systems, Asymptotic degree of random monomial ideals, Spherical Radon transform and the average of the condition number on certain Schubert subvarieties of a Grassmannian, Robust certified numerical homotopy tracking, An arithmetic Poisson formula for the multi-variate resultant, A complex analogue of Toda's theorem, Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric, Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions, On a problem posed by Steve Smale, Minimizing the discrete logarithmic energy on the sphere: The role of random polynomials, Fast computation of zeros of polynomial systems with bounded degree under finite-precision, Mixed precision path tracking for polynomial homotopy continuation, Condition length and complexity for the solution of polynomial systems, Numerical computation of the genus of an irreducible curve within an algebraic set, Probabilistic analyses of condition numbers, A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF, A note on the finite variance of the averaging function for polynomial system solving, Computing the homology of semialgebraic sets. I: Lax formulas, A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density, Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems, Complexity of Bezout's theorem. VII: Distance estimates in the condition metric, Complexity of an Homotopy Method at the Neighbourhood of a Zero, Smoothed analysis for the condition number of structured real polynomial systems, A randomized homotopy for the Hermitian eigenpair problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Kolmogorov complexity in the real Turing machine setting
• Topological complexity of a root finding algorithm
• Fixed points, zeros and Newton's method
• Estimates on the distribution of the condition number of singular matrices
• On Smale's 17th problem: a probabilistic positive solution
• Complexity of Bezout's theorem. VII: Distance estimates in the condition metric
• Probabilistic algorithm for testing primality
• Riemann's hypothesis and tests for primality
• On generalized Newton algorithms: Quadratic convergence, path-following and error analysis
• Complexity of Bezout's theorem. V: Polynomial time
• Estimations for the separation number of a polynomial system
• A universal constant for the convergence of Newton's method and an application to the classical homotopy method
• Hilbert's Nullstellensatz is in the polynomial hierarchy
• Complexity of Bezout's theorem. III: Condition number and packing
• On the probability distribution of condition numbers of complete intersection varieties and the average radius of convergence of Newton's method in the underdetermined case
• A taxonomy of problems with fast parallel algorithms
• TIME BOUNDED COMPUTATIONS OVER THE REALS
• Complexity of Bezout's Theorem I: Geometric Aspects
• A Fast Monte-Carlo Test for Primality
• Erratum: A Fast Monte-Carlo Test for Primality
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• The best bounds in Gautschi's inequality
• On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
• A Note on Proper Maps
• How to find all roots of complex polynomials by Newton's method.