A Numerical Algorithm for Zero Counting. II: Distance to Ill-posedness and Smoothed Analysis

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.

References in corpus (4)

• Smoothed analysis of algorithms
• A Numerical Algorithm for Zero Counting. I: Complexity and Accuracy
• The probability that a small perturbation of a numerical analysis problem is difficult
• Adversarial Smoothed Analysis

Cited by in corpus (11)

• Computing the homology of basic semialgebraic sets in weak exponential time
• Computing the Homology of Semialgebraic Sets I: Lax Formulas
• A Numerical Algorithm for Zero Counting. III: Randomization and Condition
• Plantinga-Vegter algorithm takes average polynomial time
• Probabilistic Condition Number Estimates For Real Polynomial Systems I: A Broader Family Of Distributions
• On Łojasiewicz Inequalities and the Effective Putinar's Positivstellensatz
• On the expected number of zeros of nonlinear equations
• On the Complexity of the Plantinga-Vegter Algorithm
• Functional norms, condition numbers and numerical algorithms in algebraic geometry
• On a condition number of random polynomial systems
• Smoothed Analysis for the Condition Number of Structured Real Polynomial Systems