{
  "id": "1110.3105",
  "version": "v2",
  "published": "2011-10-14T01:55:31.000Z",
  "updated": "2012-07-19T15:08:12.000Z",
  "title": "A fast direct solver for structured linear systems by recursive skeletonization",
  "authors": [
    "Kenneth L. Ho",
    "Leslie Greengard"
  ],
  "comment": "26 pages, 13 figures, 7 tables; accepted by SIAM J Sci Comput",
  "journal": "SIAM J. Sci. Comput. 34 (5): A2507-A2532, 2012",
  "doi": "10.1137/120866683",
  "categories": [
    "math.NA"
  ],
  "abstract": "We present a fast direct solver for structured linear systems based on multilevel matrix compression. Using the recently developed interpolative decomposition of a low-rank matrix in a recursive manner, we embed an approximation of the original matrix into a larger, but highly structured sparse one that allows fast factorization and application of the inverse. The algorithm extends the Martinsson/Rokhlin method developed for 2D boundary integral equations and proceeds in two phases: a precomputation phase, consisting of matrix compression and factorization, followed by a solution phase to apply the matrix inverse. For boundary integral equations which are not too oscillatory, e.g., based on the Green's functions for the Laplace or low-frequency Helmholtz equations, both phases typically have complexity O(N) in two dimensions, where $N$ is the number of discretization points. In our current implementation, the corresponding costs in three dimensions are $O(N^{3/2})$ and $O(N \\log N)$ for precomputation and solution, respectively. Extensive numerical experiments show a speedup of $\\sim 100$ for the solution phase over modern fast multipole methods; however, the cost of precomputation remains high. Thus, the solver is particularly suited to problems where large numbers of iterations would be required. Such is the case with ill-conditioned linear systems or when the same system is to be solved with multiple right-hand sides. Our algorithm is implemented in Fortran and freely available.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-07-19T15:08:12.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "65F05",
      "65F50",
      "65R20",
      "65Y15",
      "65Z05"
    ],
    "keywords": [
      "fast direct solver",
      "structured linear systems",
      "recursive skeletonization",
      "2d boundary integral equations",
      "solution phase"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 26,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1110.3105H"
    }
  }
}