A Numerical Algorithm for Zero Counting. II: Distance to Ill-posedness and Smoothed Analysis
arXiv:0909.410129 citations
Originality Incremental advance
AI Analysis
Provides theoretical foundations for understanding the numerical stability of zero counting algorithms for real polynomial systems.
The paper establishes a Condition Number Theorem for zero counting of real polynomial systems, showing the condition number equals the inverse of the normalized distance to ill-posed systems, and derives a smoothed analysis of this condition number.
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.