{
  "id": "2301.12704",
  "version": "v1",
  "published": "2023-01-30T07:21:13.000Z",
  "updated": "2023-01-30T07:21:13.000Z",
  "title": "Algebraic Inverse Fast Multipole Method: A fast direct solver that is better than HODLR based fast direct solver",
  "authors": [
    "Vaishnavi Gujjula",
    "Sivaram Ambikasaran"
  ],
  "comment": "32 pages, 16 Figures, 13 Tables",
  "categories": [
    "math.NA",
    "cs.NA"
  ],
  "abstract": "This article presents a fast direct solver, termed Algebraic Inverse Fast Multipole Method (from now on abbreviated as AIFMM), for linear systems arising out of $N$-body problems. AIFMM relies on the following three main ideas: (i) Certain sub-blocks in the matrix corresponding to $N$-body problems can be efficiently represented as low-rank matrices; (ii) The low-rank sub-blocks in the above matrix are leveraged to construct an extended sparse linear system; (iii) While solving the extended sparse linear system, certain fill-ins that arise in the elimination phase are represented as low-rank matrices and are \"redirected\" though other variables maintaining zero fill-in sparsity. The main highlights of this article are the following: (i) Our method is completely algebraic (as opposed to the existing Inverse Fast Multipole Method~\\cite{ arXiv:1407.1572,doi:10.1137/15M1034477,TAKAHASHI2017406}, from now on abbreviated as IFMM). We rely on our new Nested Cross Approximation~\\cite{arXiv:2203.14832} (from now on abbreviated as NNCA) to represent the matrix arising out of $N$-body problems. (ii) A significant contribution is that the algorithm presented in this article is more efficient than the existing IFMMs. In the existing IFMMs, the fill-ins are compressed and redirected as and when they are created. Whereas in this article, we update the fill-ins first without affecting the computational complexity. We then compress and redirect them only once. (iii) Another noteworthy contribution of this article is that we provide a comparison of AIFMM with Hierarchical Off-Diagonal Low-Rank (from now on abbreviated as HODLR) based fast direct solver and NNCA powered GMRES based fast iterative solver. (iv) Additionally, AIFMM is also demonstrated as a preconditioner.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-01-30T07:21:13.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "65F05",
      "65F08",
      "65Y20"
    ],
    "keywords": [
      "fast direct solver",
      "algebraic inverse fast multipole method",
      "maintaining zero fill-in sparsity",
      "extended sparse linear system",
      "body problems"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 32,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}