Condition Numbers

Paul Breiding, Kathlén Kohn, Bernd SturmfelsOberwolfach 2024 · DOI · OpenAlex

Abstract

The concept of a condition number has its origin in numerical analysis. It measures how much the output value of a function we wish to evaluate can change for a small change in the input argument. In this chapter, we discuss condition numbers in the context of metric algebraic geometry. In the first section, we offer an introduction to the relevant notions for assessing errors in numerical computations.

Introduction

In the realm of numerical computing, precision is an ideal rarely met. Whether due to measurement noise, sensor limitations, or the inherent constraints of floating-point arithmetic, the inputs we feed into algorithms are often slightly perturbed. This chapter from Metric Algebraic Geometry (2024) explores the "condition number"—a fundamental mathematical metric that quantifies how these small input errors propagate into significant, and sometimes catastrophic, output discrepancies.

The Geometry of Instability

Why are some mathematical problems inherently more "difficult" or unstable than others? The authors propose a geometric answer: numerical instability is essentially a proximity problem. A problem's sensitivity is inversely proportional to its distance from a "degenerate" or "ill-posed" state. In algebraic terms, this set of bad inputs is known as the discriminant variety.

Floating-point precision parameters for various bit-depths.

In practical computing, we deal with finite precision. As shown in the table above, different bit-depths (half, single, double) define the machine epsilon ($u$), which represents the upper bound on relative error due to rounding. When a problem instance is geometrically close to a singular case—such as a matrix with no inverse or a polynomial with a double root—even these tiny rounding errors can lead to nonsensical results. The condition number $\kappa$ acts as a bridge, where $\kappa \approx 1 / \text{distance to the discriminant}$.

Core Methodologies

The text synthesizes several classical and modern techniques to formalize this geometric intuition:

  • Rice’s Formula: This classical result defines the condition number as the maximal norm of the derivative (Jacobian) of the solution function. It provides the local linear approximation of how errors grow.
  • The Eckart–Young Theorem: A cornerstone of linear algebra, this theorem is used here to prove that the distance from a matrix to the set of singular matrices is determined precisely by its smallest singular value.
  • Bombieri–Weyl Metric: To handle polynomials in projective space, where standard Euclidean distance is insufficient, the authors employ this orthogonally invariant metric. This ensures the mathematics remains consistent with how computers actually normalize and process floating-point numbers in high-dimensional spaces.

Advanced Algebraic Tools

For more complex, sparse polynomial systems, the authors introduce Euclidean Distance (ED) duality and the Cayley Trick. Computing the distance to a complex discriminant variety is often a computationally intensive task. By utilizing ED duality, researchers can transform this distance calculation into a more manageable optimization problem on a dual toric variety. This allows for the analysis of systems where only specific coefficients are allowed to vary, reflecting real-world constraints in engineering and physics.

Key Results and Benchmarks

The central "Condition Number Theorem" formalizes the relationship: the condition number is the reciprocal of the distance to the discriminant variety. The authors apply this theory to several benchmark mathematical objects:

  • Matrix Inversion: The absolute condition number for inverting a matrix $A$ is proven to be $\|A^{-1}\|^2_{op}$, which corresponds to the inverse of the smallest singular value squared ($\sigma_n^{-2}$).
  • Polynomial Root-Finding: An explicit formula is derived showing that the condition number depends on the ratio of the polynomial's coefficients to the derivative at the specific root.
  • The Fermat Cubic and Hyperdeterminants: These complex structures are used to demonstrate the limits of sparse system analysis, showing how geometric distance can be calculated even in high-degree algebraic environments.

Limitations and Future Directions

While the theoretical framework is elegant, practical implementation faces significant hurdles. The "ED degree"—a measure of the complexity of the underlying optimization problem—can explode as systems become more generic. For instance, in the case of a $2 \times 2 \times 2$ hyperdeterminant, the degree jumps from 6 to 34 when moving from a simple to a generic case, making actual computation extremely expensive.

Furthermore, much of the underlying algebraic geometry is optimized for complex numbers. However, most engineering problems occur in the real domain. While the real discriminant is a subset of the complex one, the "distance" and resulting stability can behave differently in purely real-valued contexts, suggesting a need for further refinement in real algebraic geometry metrics.

Summary updated

Abstract

Abstract The concept of a condition number has its origin in numerical analysis. It measures how much the output value of a function we wish to evaluate can change for a small change in the input argument. In this chapter, we discuss condition numbers in the context of metric algebraic geometry. In the first section, we offer an introduction to the relevant notions for assessing errors in numerical computations.
BibTeX
@inproceedings{breiding2024condition,
  author = {Paul Breiding and Kathlén Kohn and Bernd Sturmfels},
  title = {{Condition Numbers}},
  booktitle = {Oberwolfach},
  year = {2024},
  doi = {10.1007/978-3-031-51462-3\_9},
}
Figure