# Towards Universal Convergence of Backward Error in Linear System Solvers

arXiv: https://arxiv.org/abs/2604.16075 · HTML: https://mlsanity.com/paper/2604.16075/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 46 references that are in the map.
- First posted on arXiv 17 Apr 2026.

## Builds on (most cited first, 9 of 9)

- [Implicit Gradient Regularization](https://mlsanity.com/paper/2009.11162/) (2020)
- [More Asymmetry Yields Faster Matrix Multiplication](https://mlsanity.com/paper/2404.16349/) (2024)
- [Optimal Black-Box Reductions Between Optimization Objectives](https://mlsanity.com/paper/1603.05642/) (2016)
- [Stability of the Lanczos Method for Matrix Function Approximation](https://mlsanity.com/paper/1708.07788/) (2017)
- [Uniform-in-Time Weak Error Analysis for Stochastic Gradient Descent Algorithms via Diffusion Approximation](https://mlsanity.com/paper/1902.00635/) (2019)
- [Adversarial Ink: Componentwise Backward Error Attacks on Deep Learning](https://mlsanity.com/paper/2306.02918/) (2023)
- [Backward error analysis and the qualitative behaviour of stochastic optimization algorithms: Application to stochastic coordinate descent](https://mlsanity.com/paper/2309.02082/) (2023)
- [First-order algorithms converge faster than O(1/k) on convex problems](https://mlsanity.com/paper/1812.08485/) (2018)
- [The matrix-vector complexity of Ax=b](https://mlsanity.com/paper/2602.04842/) (2026)

## Built on by (most cited first, 1 of 1)

- [Well-Conditioned Oblivious Perturbations in Linear Space](https://mlsanity.com/paper/2604.23193/) (2026)

## Abstract (arXiv)

The quest for an algorithm that solves an n× n linear system in O(n2) time complexity, or O(n2 poly(1/ε)) when solving up to ε relative error, is a long-standing open problem in numerical linear algebra and theoretical computer science. There are two predominant paradigms for measuring relative error: forward error (i.e., distance from the output to the optimum solution) and backward error (i.e., distance to the nearest problem solved by the output). In most prior studies, convergence of iterative linear system solvers is measured via various notions of forward error, and as a result, depends heavily on the conditioning of the input. Yet, the numerical analysis literature has long advocated for backward error as the more practically relevant notion of approximation. In this work, we show that -- surprisingly -- the classical and simple Richardson iteration incurs at most 1/k (relative) backward error after k iterations on any positive semidefinite (PSD) linear system, irrespective of its condition number. This universal convergence rate implies an O(n2/ε) complexity algorithm for solving a PSD linear system to ε backward error, and we establish similar or better complexity when using a variety of Krylov solvers beyond Richardson. Then, by directly minimizing backward error over a Krylov subspace, we attain an even faster O(1/k2) universal rate, and we turn this into an efficient algorithm, MINBERR, with complexity O(n2/√ε). Finally, we extend this approach via normal equations to solving general linear systems in O(n2log(n)/ε) time complexity. We report strong numerical performance of our algorithms on benchmark problems.