A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis

DOI10.1007/S11784-009-0127-4MaRDI QIDQ2431382zbMATH OpenOpenAlexWikidataFDO

Authors Felipe Cucker, Teresa Krick, Gregorio Malajovich, Mario Wschebor

Publication date 13 April 2011

Published in Journal of Fixed Point Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

condition numberspolynomial systemssmoothed analysiszero counting

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10) Complexity and performance of numerical algorithms (65Y20)

Abstract: We show a Condition Number Theorem for the condition number of zero counting for real polynomial systems. That is, we show that this condition number equals the inverse of the normalized distance to the set of ill-posed systems (i.e., those having multiple real zeros). As a consequence, a smoothed analysis of this condition number follows.

Recommendations

• A numerical algorithm for zero counting. III: Randomization and condition
• A numerical algorithm for zero counting. I: Complexity and accuracy
• Smoothed analysis for the condition number of structured real polynomial systems
• The Probability That a Numerical Analysis Problem is Difficult
• A condition number theorem for underdetermined polynomial systems

Cited in

(19)

• On condition numbers and the distance to the nearest ill-posed problem
• Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions
• Grid methods in computational real algebraic (and semialgebraic) geometry
• On the complexity of the Plantinga-Vegter algorithm
• Computing the homology of semialgebraic sets. I: Lax formulas
• On the expected number of zeros of nonlinear equations
• On a condition number of general random polynomial systems
• scientific article; zbMATH DE number 3951890 (Why is no real title available?)
• The Probability That a Numerical Analysis Problem is Difficult
• Spherical Radon transform and the average of the condition number on certain Schubert subvarieties of a Grassmannian
• Smoothed analysis for the condition number of structured real polynomial systems
• Functional norms, condition numbers and numerical algorithms in algebraic geometry
• A theory of complexity, condition, and roundoff
• On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers
• Newton iteration, conditioning and zero counting
• A numerical algorithm for zero counting. III: Randomization and condition
• On Łojasiewicz inequalities and the effective Putinar's Positivstellensatz
• Computing the homology of real projective sets
• A numerical algorithm for zero counting. I: Complexity and accuracy

This page was built for publication: A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2431382)