The matrix-vector complexity of $Ax=b$

Michał Dereziński; Ethan N. Epperly; Raphael A. Meyer

The matrix-vector complexity of $Ax=b$

Michał Dereziński, Ethan N. Epperly, Raphael A. Meyer

arXivarxiv/2602.04842Feb 4, 2026cs.DSscore 0

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…

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2602.04842
curl -X POST /api/v1/records/arxiv/2602.04842/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.04842/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'