{
  "$type": "site.standard.document",
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.04842v1",
  "publishedAt": "2026-02-05T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Michał Dereziński",
    "Ethan N. Epperly",
    "Raphael A. Meyer"
  ],
  "textContent": "**Authors:** Michał Dereziński, Ethan N. Epperly, Raphael A. Meyer\n\nMatrix-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 a matrix-vector algorithm which 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$"
}