The matrix-vector complexity of $Ax=b$
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908838903414784 |
|---|---|
| author | Dereziński, Michał Epperly, Ethan N. Meyer, Raphael A. |
| author_facet | Dereziński, Michał Epperly, Ethan N. Meyer, Raphael A. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_04842 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The matrix-vector complexity of $Ax=b$ Dereziński, Michał Epperly, Ethan N. Meyer, Raphael A. Data Structures and Algorithms Numerical Analysis Optimization and Control 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. |
| title | The matrix-vector complexity of $Ax=b$ |
| topic | Data Structures and Algorithms Numerical Analysis Optimization and Control |
| url | https://arxiv.org/abs/2602.04842 |