On a problem posed by Steve Smale

DOI10.4007/annals.2011.174.3.8zbMath1248.65047arXiv0909.2114WikidataQ30000094 ScholiaQ30000094MaRDI QIDQ661924

Felipe Cucker, Peter Bürgisser

Publication date: 11 February 2012

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

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

zbMATH Keywords

complexity; complex polynomials; randomized algorithm; approximate zero; polynomial time; deterministic algorithm; polynomial equation solving; smoothed analysis; linear homotopy algorithm

Mathematics Subject Classification ID

65H10: Numerical computation of solutions to systems of equations

30C15: Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)

65E05: General theory of numerical methods in complex analysis (potential theory, etc.)

65Y20: Complexity and performance of numerical algorithms

30C10: Polynomials and rational functions of one complex variable

65H04: Numerical computation of roots of polynomial equations

Related Items

Functional norms, condition numbers and numerical algorithms in algebraic geometry, A sequence of polynomials with optimal condition number, A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF, Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems, Fast computation of zeros of polynomial systems with bounded degree under finite-precision, Probabilistic analyses of condition numbers, Rigid continuation paths II. structured polynomial systems, Random sampling in computational algebra: Helly numbers and violator spaces, On the zeta Mahler measure function of the Jacobian determinant, condition numbers and the height of the generic discriminant, Smale's fundamental theorem of algebra reconsidered, Complexity of path-following methods for the eigenvalue problem, Spherical Radon transform and the average of the condition number on certain Schubert subvarieties of a Grassmannian, A complex analogue of Toda's theorem, The unavoidable condition\dots A report on the book. Book review of: P. Bürgisser and F. Cucker, Condition. The geometry of numerical algorithms, Foreword. What is numerical algebraic geometry?, Globally convergent, iterative path-following for algebraic equations, Random monomial ideals, A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time, 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 the geometry and topology of the solution variety for polynomial system solving, Robust certified numerical homotopy tracking, Mixed precision path tracking for polynomial homotopy continuation, Computing the homology of semialgebraic sets. I: Lax formulas, A randomized homotopy for the Hermitian eigenpair problem, An arithmetic Poisson formula for the multi-variate resultant, Condition numbers for the cube. I: Univariate polynomials and hypersurfaces, The average condition number of most tensor rank decomposition problems is infinite, The Legacy of Turing in Numerical Analysis, Smale 17th Problem: Advances and Open Directions, Structure and Optimisation in Computational Harmonic Analysis: On Key Aspects in Sparse Regularisation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast linear homotopy to find approximate zeros of polynomial systems
• Robust smoothed analysis of a condition number for linear programming
• Smoothed analysis of complex conic condition numbers
• On Smale's 17th problem: a probabilistic positive solution
• Adversarial smoothed analysis
• Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric
• Complexity of Bezout's theorem. VII: Distance estimates in the condition metric
• Probabilistic algorithm for testing primality
• The complexity of partial derivatives
• Complexity of Bezout's theorem. V: Polynomial time
• PRIMES is in P
• Smoothed analysis of \(\kappa(A)\)
• Complexity of Bezout's theorem. III: Condition number and packing
• Smale’s 17th problem: Average polynomial time to compute affine and projective solutions
• Smoothed Analysis of Moore–Penrose Inversion
• Smoothed analysis of some condition numbers
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• The probability that a slightly perturbed numerical analysis problem is difficult
• On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
• Complexity of Bezout's Theorem I: Geometric Aspects
• A Fast Monte-Carlo Test for Primality
• The kinematic formula in Riemannian homogeneous spaces
• On the Medians of Gamma Distributions and an Equation of Ramanujan
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• 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