On a problem posed by Steve Smale

DOI10.4007/annals.2011.174.3.8zbMath1248.65047arXiv0909.2114OpenAlexW2120280171WikidataQ30000094 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

complexitycomplex polynomialsrandomized algorithmapproximate zeropolynomial timedeterministic algorithmpolynomial equation solvingsmoothed analysislinear homotopy algorithm

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) General theory of numerical methods in complex analysis (potential theory, etc.) (65E05) Complexity and performance of numerical algorithms (65Y20) Polynomials and rational functions of one complex variable (30C10) Numerical computation of roots of polynomial equations (65H04)

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, Condition numbers for the cube. I: Univariate polynomials and hypersurfaces, 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, Rigid continuation paths II. structured 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, The average condition number of most tensor rank decomposition problems is infinite, Robust certified numerical homotopy tracking, An arithmetic Poisson formula for the multi-variate resultant, A complex analogue of Toda's theorem, Globally convergent, iterative path-following for algebraic equations, 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, A sequence of polynomials with optimal condition number, The unavoidable condition\dots A report on the book. Book review of: P. Bürgisser and F. Cucker, Condition. The geometry of numerical algorithms, Fast computation of zeros of polynomial systems with bounded degree under finite-precision, Mixed precision path tracking for polynomial homotopy continuation, Foreword. What is numerical algebraic geometry?, Probabilistic analyses of condition numbers, A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF, Computing the homology of semialgebraic sets. I: Lax formulas, Smale 17th Problem: Advances and Open Directions, Structure and Optimisation in Computational Harmonic Analysis: On Key Aspects in Sparse Regularisation, Rigid continuation paths I. Quasilinear average complexity for solving 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
• 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