The probability that a slightly perturbed numerical analysis problem is difficult

DOI10.1090/S0025-5718-08-02060-7zbMath1195.65018arXivmath/0610270OpenAlexW2005724489WikidataQ57733157 ScholiaQ57733157MaRDI QIDQ3577011

Martin Lotz, Felipe Cucker, Peter Bürgisser

Publication date: 3 August 2010

Published in: Mathematics of Computation (Search for Journal in Brave)

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

zbMATH Keywords

condition numberspolynomial equationsmooth analysistubular neighborhoods of algebraic surfaces

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Complexity and performance of numerical algorithms (65Y20)

Related Items

Average-case complexity without the black swans ⋮ Smooth analysis of the condition number and the least singular value ⋮ Smoothed Analysis of Local Search Algorithms ⋮ On the complexity of the Plantinga-Vegter algorithm ⋮ Hausdorff approximations and volume of tubes of singular algebraic sets ⋮ A numerical algorithm for zero counting. III: Randomization and condition ⋮ On a problem posed by Steve Smale ⋮ Robust smoothed analysis of a condition number for linear programming ⋮ Generalizations of the Kolmogorov-Barzdin embedding estimates ⋮ Probabilistic analyses of condition numbers ⋮ On the volume of tubular neighborhoods of real algebraic varieties ⋮ Adversarial smoothed analysis ⋮ A formal proof of the expressiveness of deep learning ⋮ A formal proof of the expressiveness of deep learning ⋮ Computing the homology of semialgebraic sets. I: Lax formulas ⋮ From Steiner formulas for cones to concentration of intrinsic volumes ⋮ On local analysis ⋮ Probabilistic analysis of the Grassmann condition number

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on level-2 condition numbers
• Smoothed analysis of complex conic condition numbers
• Estimates on the distribution of the condition number of singular matrices
• On condition numbers and the distance to the nearest ill-posed problem
• Volumes of tubular neighbourhoods of real algebraic varieties
• Complexity of Bezout's theorem. V: Polynomial time
• Smoothed analysis of termination of linear programming algorithms
• Generalized inverses. Theory and applications.
• Smoothed analysis of \(\kappa(A)\)
• Complexity of Bezout's theorem. III: Condition number and packing
• General formulas for the smoothed analysis of condition numbers
• Note on matrices with a very ill-conditioned eigenproblem
• Smoothed analysis of some condition numbers
• Smoothed analysis of algorithms
• The Probability That a Numerical Analysis Problem is Difficult
• The fundamental theorem of algebra and complexity theory
• Complexity of Bezout's Theorem I: Geometric Aspects
• The kinematic formula in Riemannian homogeneous spaces
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
• On the Betti Numbers of Real Varieties
• On the Volume of Tubes
• Numerical inverting of matrices of high order
• ROUNDING-OFF ERRORS IN MATRIX PROCESSES