🔢 mathematics

Perturbation Analysis for Preconditioned Normal Equations in Mixed Precision

This paper analyzes the conditioning of various preconditioned normal equations using randomized preconditioners computed in lower precision, demonstrating that solution accuracy depends mildly on preconditioner quality but significantly on the least squares residual, while proposing an automatic precision selection method that achieves efficiency and accuracy comparable to MATLAB's mldivide, particularly on GPUs.

Original authors: James E. Garrison, Ilse C. F. Ipsen

Published 2026-03-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: James E. Garrison, Ilse C. F. Ipsen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the perfect route through a massive, foggy city to get to a specific destination. This is what mathematicians call a Least Squares Problem: you have a bunch of data points (the foggy streets) and you want to find the single best path (the solution) that gets you closest to your goal, even if the data is messy or imperfect.

The paper by Garrison and Ipsen is about a new, smarter way to navigate this city, especially when the city is huge and the maps are blurry.

Here is the breakdown of their work using simple analogies:

1. The Problem: The "Squaring" Trap

Usually, to solve these navigation problems, mathematicians use a method called Normal Equations. Think of this like trying to flatten a 3D map onto a 2D piece of paper to make it easier to read.

The Catch: When you flatten the map, the details get distorted. If the original map was already a bit tricky (ill-conditioned), flattening it makes it a nightmare. The "noise" in the data gets squared, turning a small error into a huge disaster. It's like trying to read a blurry photo after zooming in 100 times; it just gets worse.

2. The Old Solution: The "Perfect" Preconditioner

To fix the distortion, experts use a Preconditioner. Imagine this as a special pair of glasses or a lens that you put over your map before you flatten it. These glasses straighten out the lines so that when you flatten the map, it stays clear.

The Issue: Making these perfect glasses usually takes a long time and requires high-quality materials (high-precision math). It's like hiring a master optician to hand-craft your lenses. It's accurate, but slow and expensive.

3. The New Idea: "Good Enough" Glasses Made Quickly

The authors ask: What if we made the glasses quickly using cheaper materials (lower precision), and then used them to solve the problem?

The Fear: Everyone thought that if the glasses were made cheaply (in "single precision" or "half precision" math), they would be too blurry to help. The math would be ruined.
The Discovery: The authors proved that this fear is mostly wrong. Even if the glasses are a little bit blurry (computed in lower precision), they still straighten out the map enough to find the correct path. The final result is almost as accurate as if you had used the expensive, perfect glasses.

4. The "Mixed Precision" Magic

The paper introduces a strategy called Mixed Precision.

The Analogy: Imagine you are building a house. You don't need to measure the foundation with a laser micrometer (double precision) if you are just hammering in the nails (single precision).
How it works:
1. Step 1 (The Quick Scan): They use a fast, low-precision tool to quickly estimate how "twisted" the map is.
2. Step 2 (The Smart Choice): Based on that quick scan, they automatically decide: "Okay, this map is simple, let's use cheap, fast glasses." OR "This map is a nightmare, let's use the expensive glasses."
3. Step 3 (The Execution): They solve the problem. The heavy lifting is done with the cheap, fast glasses, but the final result is polished in high precision.

5. Why This Matters (The "GPU" Connection)

The paper tests this on GPUs (the powerful chips in graphics cards and supercomputers).

The Metaphor: GPUs are like a thousand tiny workers who are great at doing simple, fast tasks but bad at slow, complex ones.
The Result: By using the "cheap glasses" (low precision) for the heavy lifting, the workers can move much faster. The authors show that on modern NVIDIA GPUs, this method is significantly faster than traditional methods, while still giving you a solution that is just as accurate as the slow, expensive way.

6. The "Residual" Surprise

One of the most interesting findings is about the Residual (the leftover error).

The Analogy: Imagine you are trying to hit a bullseye.
- If you are way off target (a huge residual), the quality of your glasses doesn't matter much; you're going to miss anyway.
- If you are almost on target (a small residual), the glasses matter a lot.
The Insight: The authors found that the accuracy of their method depends heavily on how close you already are to the solution. If you are already close, even the "cheap glasses" work perfectly. If you are far off, the method behaves exactly as expected.

Summary

This paper is like a guide for smart navigation. It tells us that we don't always need the most expensive, slowest tools to get a perfect result. By using a mix of fast, low-quality tools and a smart strategy to decide when to use them, we can solve massive mathematical problems much faster on modern computers without losing accuracy.

It's the difference between hiring a team of snails to measure a room inch-by-inch versus hiring a team of cheetahs with a tape measure who can do a "good enough" job in a split second. The paper proves that for many tasks, the cheetahs win.

1. Problem Statement

The paper addresses the numerical stability and conditioning of solving least squares problems $\min_x \|Ax - b\|_2$ using Normal Equations ( $A^T Ax = A^T b$ ).

The Challenge: Normal equations are often discouraged because squaring the matrix $A$ to form $A^T A$ squares the condition number ( $\kappa(A^T A) = \kappa(A)^2$ ). If $\kappa(A)$ is large (e.g., $>10^7$ ), $A^T A$ becomes numerically singular in double precision.
The Context: Preconditioning is a standard technique to improve conditioning. However, existing perturbation bounds for preconditioned normal equations assume the preconditioner is computed in the same high precision as the solver.
The Gap: There is a lack of rigorous error analysis for mixed-precision scenarios where a randomized preconditioner is computed in lower precision (e.g., single or half precision) to accelerate computation, while the main solve occurs in double precision. The authors aim to determine if the loss of precision in the preconditioner degrades the solution accuracy and to provide realistic error bounds.

2. Methodology

The authors analyze four specific formulations of preconditioned systems where a randomized preconditioner $R_s$ (computed in lower precision) is applied to matrix $A$ :

Preconditioned Normal Equations (PNE): Solve $A_p^T A_p y = A_p^T b$ where $A_p = A R_s^{-1}$ , then recover $x = R_s^{-1} y$ .
Half-Preconditioned Normal Equations (HPNE): Solve $A_p^T A x = A_p^T b$ . This avoids solving a triangular system for $y$ but results in a non-symmetric system.
Seminormal Equations: Solving $R^T R x = A^T b$ derived from a QR factorization.
Not-Normal Equations: Solving $B^T A x = B^T b$ where $B$ shares the column space of $A$ .

Key Theoretical Approach:

Perturbation Analysis: The authors derive new perturbation bounds for the relative error $\frac{\|\hat{x} - x^*\|}{\|\hat{x}\|}$ .
Mixed Precision Modeling: They explicitly model the error introduced by computing the preconditioner $R_s$ in lower precision (denoted as perturbation $E_s$ ) and the matrix $A$ in working precision (perturbation $E_A$ ).
Randomized Sketching: They utilize a randomized preconditioner based on sketching (subsampled trigonometric transforms) to reduce $A$ to a smaller matrix, from which $R_s$ is extracted via QR factorization.

3. Key Contributions

A. New Perturbation Bounds (Theorems 3.2 and 4.2)

The most significant contribution is the derivation of realistic and informative perturbation bounds for PNE and HPNE in mixed precision.

Independence from Preconditioner Precision: Unlike previous bounds, the new bounds show that the solution accuracy depends only mildly on the precision of the preconditioner ( $R_s$ ), provided the preconditioner is nonsingular.
Dependence on Residuals: The bounds reveal that accuracy depends heavily on the size of the least squares residual ( $\|Ax - b\|$ $∥ A x - b ∥$ ).
- If the residual is small, the solution is highly accurate.
- If the residual is large, the error grows, but the bounds remain tight and informative.
Comparison to Old Bounds: The authors demonstrate that previous bounds (e.g., from [12]) become "uninformative" (severe overestimates) when the preconditioner is computed in low precision because they fail to account for the specific structure of the mixed-precision error.

B. Analysis of Alternative Equations

Seminormal Equations: The authors prove that seminormal equations are no better conditioned than standard normal equations; their error bounds still depend on $\kappa(A)^2$ and the residual size.
Not-Normal Equations: They show these are well-conditioned when the matrix $B$ is close to the preconditioned matrix $A_p$ , with error behavior similar to HPNE.

C. Automatic Precision Selection (Algorithm 6.1)

The paper proposes a practical algorithm to automatically select the precision level (Half, Single, or Double) for computing the preconditioner based on a fast condition number estimation of $A$ in single precision:

If $\log_{10}(\kappa(A)) < 4$ : Use Half Precision.
If $4 \le \log_{10}(\kappa(A)) \le 8$ : Use Single Precision.
If $\log_{10}(\kappa(A)) > 8$ : Use Double Precision.
This ensures the preconditioner is accurate enough to keep $\kappa(A_p) \lesssim 10$ without wasting computational resources.

4. Results and Numerical Experiments

The authors validate their theory using NVIDIA H100 GPUs and standard benchmarks:

Accuracy vs. Residuals:
- In Double Precision, the new bounds (Theorems 3.2/4.2) tightly track the actual error, whereas old bounds overestimate it.
- In Mixed Precision (Single precision preconditioner, Double precision solve), the new bounds correctly predict that the solution remains accurate even for ill-conditioned matrices ( $\kappa(A) = 10^8$ ), provided the least squares residual is not extremely small (where the relative error might be slightly higher than standard solvers, but still acceptable).
- For large residuals, the mixed-precision PNE/HPNE solutions achieve accuracy comparable to Matlab's mldivide (QR-based solver).
Performance (GPU):
- Speedup: Mixed-precision PNE/HPNE on an NVIDIA H100 GPU shows speedups over standard double-precision QR solvers, particularly for matrices with fewer columns ( $n \le 2000$ ).
- Memory: The approach offers a reduced memory footprint, a critical advantage for large-scale problems.
- Scalability: As the number of columns increases, the sketching cost dominates, and the speed advantage diminishes, but the mixed-precision approach remains competitive.

5. Significance

Theoretical Advancement: The paper resolves the ambiguity regarding the stability of mixed-precision preconditioning for normal equations. It proves that one can safely compute preconditioners in lower precision without sacrificing the robustness of the solution, provided the residual is not vanishingly small.
Practical Impact: The findings enable the use of low-precision hardware (like Tensor Cores on GPUs) for the expensive preconditioning step, significantly accelerating least squares solvers for large-scale, ill-conditioned problems.
Algorithmic Efficiency: The proposed automatic precision selection heuristic allows solvers to adapt dynamically to the problem's conditioning, optimizing the trade-off between speed and accuracy.

In summary, Garrison and Ipsen provide the theoretical justification and practical algorithms to make mixed-precision preconditioned normal equations a viable, efficient, and accurate alternative to traditional QR-based solvers, particularly in high-performance computing environments.