# Solving Sparse Linear Systems Faster than Matrix Multiplication

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jul 2020.

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

- [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023)
- [Testing Calibration in Nearly-Linear Time](https://mlsanity.com/paper/2402.13187/) (2024)
- [Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems](https://mlsanity.com/paper/2405.05818/) (2024)
- [FairWASP: Fast and Optimal Fair Wasserstein Pre-processing](https://mlsanity.com/paper/2311.00109/) (2023)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [Towards Neural Sparse Linear Solvers](https://mlsanity.com/paper/2203.06944/) (2022)
- [Gradient Coding with Iterative Block Leverage Score Sampling](https://mlsanity.com/paper/2308.03096/) (2023)
- [Randomized Schur Complement Views for Graph Contrastive Learning](https://mlsanity.com/paper/2306.04004/) (2023)
- [HERTA: A High-Efficiency and Rigorous Training Algorithm for Unfolded Graph Neural Networks](https://mlsanity.com/paper/2403.18142/) (2024)
- [Well-Conditioned Oblivious Perturbations in Linear Space](https://mlsanity.com/paper/2604.23193/) (2026)

## Abstract (arXiv)

Can linear systems be solved faster than matrix multiplication? While there has been remarkable progress for the special cases of graph structured linear systems, in the general setting, the bit complexity of solving an n × n linear system Ax=b is tildeO(nω), where ω < 2.372864 is the matrix multiplication exponent. Improving on this has been an open problem even for sparse linear systems with poly(n) condition number. In this paper, we present an algorithm that solves linear systems in sparse matrices asymptotically faster than matrix multiplication for any ω > 2. This speedup holds for any input matrix A with o(nω -1/log(kappa(A))) non-zeros, where kappa(A) is the condition number of A. For poly(n)-conditioned matrices with tildeO(n) nonzeros, and the current value of ω, the bit complexity of our algorithm to solve to within any 1/poly(n) error is O(n2.331645). Our algorithm can be viewed as an efficient, randomized implementation of the block Krylov method via recursive low displacement rank factorizations. It is inspired by the algorithm of [Eberly et al. ISSAC `06 `07] for inverting matrices over finite fields. In our analysis of numerical stability, we develop matrix anti-concentration techniques to bound the smallest eigenvalue and the smallest gap in eigenvalues of semi-random matrices.