The matrix-vector complexity of $Ax=b$
For researchers and practitioners using iterative solvers, this work provides rigorous lower bounds that confirm the optimality of widely used Krylov subspace methods.
This paper proves lower bounds on the number of matrix-vector products needed to solve linear systems, showing that two-sided algorithms require Ω(κ log(1/ε)) products (matching conjugate gradient) and one-sided algorithms require n products even for well-conditioned systems, with constants matching known upper bounds within a factor of four.
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 condition number $κ$ 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 \times 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.