{
  "id": "2110.05351",
  "version": "v2",
  "published": "2021-10-11T15:29:12.000Z",
  "updated": "2022-12-19T23:40:28.000Z",
  "title": "Sparse recovery of elliptic solvers from matrix-vector products",
  "authors": [
    "Florian Schäfer",
    "Houman Owhadi"
  ],
  "categories": [
    "math.NA",
    "cs.NA"
  ],
  "abstract": "In this work, we show that solvers of elliptic boundary value problems in $d$ dimensions can be approximated to accuracy $\\epsilon$ from only $O\\left(\\log(N)\\log^{d}(N / \\epsilon)\\right)$ matrix-vector products with carefully chosen vectors (right-hand sides). The solver is only accessed as a black box, and the underlying operator may be unknown and of an arbitrarily high order. Our algorithm (1) has complexity $O\\left(N\\log^2(N)\\log^{2d}(N / \\epsilon)\\right)$ and represents the solution operator as a sparse Cholesky factorization with $O\\left(N\\log(N)\\log^{d}(N / \\epsilon)\\right)$ nonzero entries, (2) allows for embarrassingly parallel evaluation of the solution operator and the computation of its log-determinant, (3) allows for $O\\left(\\log(N)\\log^{d}(N / \\epsilon)\\right)$ complexity computation of individual entries of the matrix representation of the solver that, in turn, enables its recompression to an $O\\left(N\\log^{d}(N / \\epsilon)\\right)$ complexity representation. As a byproduct, our compression scheme produces a homogenized solution operator with near-optimal approximation accuracy. By polynomial approximation, we can also approximate the continuous Green's function (in operator and Hilbert-Schmidt norm) to accuracy $\\epsilon$ from $O\\left(\\log^{1 + d}\\left(\\epsilon^{-1}\\right)\\right)$ solutions of the PDE. We include rigorous proofs of these results. To the best of our knowledge, our algorithm achieves the best-known trade-off between accuracy $\\epsilon$ and the number of required matrix-vector products.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2022-12-19T23:40:28.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "65N55",
      "65N22",
      "65N15"
    ],
    "keywords": [
      "matrix-vector products",
      "sparse recovery",
      "elliptic solvers",
      "solution operator",
      "elliptic boundary value problems"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}