{"id":"arxiv/2602.04842","url":"https://arxiv.org/abs/2602.04842","tags":["cs.DS","math.NA","math.OC"],"score":0,"title":"The matrix-vector complexity of $Ax=b$","domain":"cs.DS","source":"arxiv","authors":["Michał Dereziński","Ethan N. Epperly","Raphael A. Meyer"],"reviews":0,"subject":"cs.DS","summary":"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, $Ω(κ\\log(1/\\varepsilon))$ matrix--vector products are necessary to solve a linear system with…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-02-04","reactions":{}}