# The matrix-vector complexity of Ax=b

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Feb 2026.

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

- [Towards Universal Convergence of Backward Error in Linear System Solvers](https://mlsanity.com/paper/2604.16075/) (2026)
- [Well-Conditioned Oblivious Perturbations in Linear Space](https://mlsanity.com/paper/2604.23193/) (2026)

## Abstract (arXiv)

Matrix--vector algorithms, particularly Krylov subspace methods, are widely viewed as the most effective algorithms for solving large systems of linear equations. This paper establishes lower bounds on the worst-case number of matrix--vector products needed by such an algorithm to approximately solve a general linear system. The first main result is that, for any matrix--vector algorithm which is allowed the use of randomization and can perform products with both a matrix and its transpose, Omega(kappa log(1/varepsilon)) matrix--vector products are necessary to solve a linear system with condition number kappa to accuracy varepsilon, matching an upper bound for conjugate gradient on the normal equations. The second main result is that one-sided algorithms, which lack access to the transpose, must use n matrix--vector products to solve an n × n linear system, even when the problem is perfectly conditioned. Both main results include explicit constants that match known upper bounds up to a factor of four. These results rigorously demonstrate the limitations of matrix--vector algorithms and confirm the optimality of widely used Krylov subspace algorithms.