Abstract
Condition is the main aspect in the understanding of the performance — regarding both stability and complexity — of numerical algorithms. Global insights into the quality of such algorithms can be obtained by a probabilistic analysis, assuming the data is random (e.g., subject to random perturbations). Often, a clean analysis can be obtained via a probabilistic analysis of the corresponding condition. This methodology can be applied in a wide variety of contexts, including linear algebra, convex optimization, and solving polynomial equations.