Stable algorithms for general linear systems by preconditioning the normal equations

Ethan N. Epperly, Anne Greenbaum, Yuji Nakatsukasa

TL;DR

This paper tackles the challenge of solving large, nonsymmetric linear systems using preconditioned iterative methods, specifically focusing on LSQR. They demonstrate that while LSQR can suffer from significant accuracy issues, a simple technique called iterative refinement, when applied judiciously, can restore backward stability and achieve high accuracy, even for ill-conditioned problems.

What Problem Does This Paper Address?

Solving linear systems of equations ($Ax = b$) is a fundamental problem in scientific computing. For large systems, iterative methods like Krylov subspace methods (e.g., GMRES, LSQR) are often preferred over direct methods due to their lower memory requirements and potential for faster convergence. Preconditioning is a crucial technique to accelerate these iterative methods by transforming the original system into one that is easier to solve.

However, for nonsymmetric linear systems, especially those that are ill-conditioned, standard preconditioned iterative methods can exhibit poor numerical stability, leading to solutions that are orders of magnitude less accurate than direct solvers. This paper specifically investigates preconditioned LSQR, a method that implicitly solves the normal equations. While LSQR is known for its efficiency, it can be particularly susceptible to numerical errors when dealing with ill-conditioned problems, even with a good preconditioner. The core problem addressed is how to achieve reliable and accurate solutions for nonsymmetric linear systems using preconditioned LSQR, bridging the gap between theoretical expectations and practical numerical behavior.

Methods

The paper's central contribution lies in demonstrating how to achieve backward stable solutions for nonsymmetric linear systems using preconditioned LSQR. The key techniques are:

  • Preconditioning the Normal Equations: Instead of directly solving $Ax=b$, the paper considers solving the equivalent system derived from the normal equations: $(P^{-T}A^T A P^{-1})y = P^{-T}A^Tb$, where $x = P^{-1}y$ and $P$ is a preconditioner. This approach is motivated by the idea that designing an "LSQR-good" preconditioner (one that makes $AP^{-1}$ near-orthogonal) might be easier than designing a "GMRES-good" preconditioner (one that makes $AP^{-1}$ near-inverse).
  • Iterative Refinement (IR): The paper proposes using iterative refinement as a post-processing step for LSQR. After an initial LSQR solve, the residual is computed, and if it hasn't reached the desired accuracy, a correction is computed and added to the solution. This process can be repeated. The authors show that even a single step of iterative refinement can dramatically improve accuracy.
  • Automatic Restarting/Termination: To make iterative refinement practical, the paper introduces an automatic procedure that monitors the backward error. If the backward error stagnates or fails to improve sufficiently, the algorithm triggers an iterative refinement step. This avoids manual tuning of restart frequencies.
  • Backward Error Analysis: A significant portion of the paper is dedicated to rigorous backward error analysis. This analysis aims to prove that the proposed methods produce solutions that are exact for a slightly perturbed version of the original problem, which is the definition of backward stability. They analyze the error propagation through the preconditioning and iterative steps.
  • Left-Preconditioning: The paper also explores left-preconditioned LSQR ($P^{-1}Ax = P^{-1}b$). Interestingly, they observe that this variant appears to be backward stable even without iterative refinement, a surprising empirical finding that warrants further theoretical investigation.

Datasets

Not discussed in the paper. The paper uses synthetic matrices generated for experimental purposes to illustrate the behavior of the algorithms.

Key Insights and Ideas

  • Iterative Refinement is Key for LSQR Stability: The most striking insight is that preconditioned LSQR, while potentially fast, can be numerically unstable and produce highly inaccurate results for ill-conditioned problems. However, iterative refinement, even a single step, can restore backward stability and achieve machine precision accuracy. This makes LSQR a viable option where it was previously considered too unreliable.
  • "LSQR-Good" vs. "GMRES-Good" Preconditioners: The authors propose a new perspective on preconditioning: it's easier to find a preconditioner that makes $AP^{-1}$ "near-orthogonal" (good for LSQR) than one that makes it "near-inverse" (good for GMRES). This suggests a broader design space for LSQR preconditioners.
  • Left-Preconditioning Surprise: The empirical observation that left-preconditioned LSQR seems to be backward stable without iterative refinement is a significant finding. This suggests a potential avenue for simpler, stable solvers in certain scenarios, though it lacks a theoretical explanation in this work.
  • Backward Stability is Achievable: The paper provides a theoretical framework and proofs demonstrating that with iterative refinement and a good preconditioner, LSQR can achieve backward stability for nonsymmetric linear systems. This is a crucial step towards making iterative methods as reliable as direct solvers.

Key Results

  • Dramatic Accuracy Improvement: In experiments with ill-conditioned matrices, preconditioned LSQR without iterative refinement produced errors many orders of magnitude larger than direct methods. With just one step of iterative refinement, the forward error improved by five orders of magnitude, reaching machine precision.
  • Theoretical Guarantees: The paper establishes theoretical results (Informal Theorem 1.1 and Theorem 6.3) showing that the proposed preconditioned LSQR with iterative refinement (PLSQR-IR) can achieve backward stability. This requires a number of iterative refinement steps proportional to $\log(1/\kappa u)$, where $\kappa$ is the condition number and $u$ is the machine precision.
  • Left-Preconditioned LSQR Stability: Empirically, left-preconditioned LSQR was shown to achieve backward stability without iterative refinement on tested examples, even for matrices with condition numbers up to $10^{10}$.
  • Comparison with GMRES: The paper provides a nuanced discussion of LSQR versus GMRES, highlighting scenarios where each method excels and suggesting that LSQR, with proper preconditioning and iterative refinement, can be a competitive alternative.

Limitations and Future Work

  • Theoretical Explanation for Left-Preconditioning: The paper notes that while left-preconditioned LSQR shows strong empirical stability, a theoretical explanation for this phenomenon is lacking and is a subject for future work.
  • Analysis of Preconditioner Design: While the paper argues for the ease of designing LSQR-good preconditioners, it doesn't delve deeply into the practical construction of such preconditioners beyond mentioning general ideas.
  • Generalization of Iterative Refinement: The paper focuses on LSQR-IR but mentions that iterative refinement can also improve the accuracy of preconditioned conjugate gradient for symmetric positive definite systems, suggesting this as a direction for future research.
  • Practical Implementation of Lanczos: The theoretical analysis relies on the Lanczos method for solving the preconditioned normal equations. While they provide pseudocode for an implementation of PLSQR-IR, the practical implications and performance of using Lanczos (especially with its storage requirements) in this context could be further explored.
  • More Extensive Numerical Testing: While the paper includes illustrative examples, more extensive numerical testing across a wider range of problem types and sizes would further solidify the findings.

Summary updated

Abstract

This paper studies the solution of nonsymmetric linear systems by preconditioned Krylov methods based on the normal equations, LSQR in particular. On some examples, preconditioned LSQR is seen to produce errors many orders of magnitude larger than classical direct methods; this paper demonstrates that the attainable accuracy of preconditioned LSQR can be greatly improved by applying iterative refinement or restarting when the accuracy stalls. This observation is supported by rigorous backward error analysis. This paper also provides a discussion of the relative merits of GMRES and LSQR for solving nonsymmetric linear systems, demonstrates stability for left-preconditioned LSQR without iterative refinement, and shows that iterative refinement can also improve the accuracy of preconditioned conjugate gradient.
BibTeX
@article{epperly2026stable,
  author = {Ethan N. Epperly and Anne Greenbaum and Yuji Nakatsukasa},
  title = {{Stable algorithms for general linear systems by preconditioning the normal equations}},
  journal = {Numerische Mathematik},
  year = {2026},
  doi = {10.1007/s00211-026-01547-1},
}
Figure