The probability that a slightly perturbed numerical analysis problem is difficult

DOI10.1090/S0025-5718-08-02060-7zbMath1195.65018arXivmath/0610270WikidataQ57733157 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 numbers; polynomial equation; smooth analysis; tubular neighborhoods of algebraic surfaces

Mathematics Subject Classification ID

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

65H20: Global methods, including homotopy approaches to the numerical solution of nonlinear equations

65Y20: Complexity and performance of numerical algorithms

Related Items

On the volume of tubular neighborhoods of real algebraic varieties, Probabilistic analyses of condition numbers, A formal proof of the expressiveness of deep learning, A formal proof of the expressiveness of deep learning, 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, From Steiner formulas for cones to concentration of intrinsic volumes, Adversarial smoothed analysis, Generalizations of the Kolmogorov-Barzdin embedding estimates, On the complexity of the Plantinga-Vegter algorithm, Computing the homology of semialgebraic sets. I: Lax formulas, On local analysis, Probabilistic analysis of the Grassmann condition number, Average-case complexity without the black swans, Smooth analysis of the condition number and the least singular value, Smoothed Analysis of Local Search Algorithms

Cites Work

• 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
• 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