A recursive skeletonization factorization based on strong admissibility

Victor Minden (Computational Neuroscience, Flatiron Institute)

Many problems in the computational physical sciences are phrased as elliptic partial differential equations that can be recast as integral equations over the boundary or volume of the domain and then discretized. To solve the resulting dense linear systems efficiently, we introduce the strong recursive skeletonization factorization (RS-S), a new approximate matrix factorization based on recursive skeletonization that is suitable for use as a moderate-accuracy direct solver or preconditioner – in effect, serving as an approximate inverse of the fast multipole method (FMM). Like recursive skeletonization, our method identifies and compresses low-rank submatrices using an interpolative decomposition. However, to avoid high-rank submatrices we compress only far-field kernel interactions using the same matrix structure as the FMM. This yields an approximate factorization of the inverse operator in the form of a product of many block unit-triangular matrices. Under suitable rank assumptions RS-S exhibits linear computational complexity, which we demonstrate with a number of academic numerical examples. This is joint work with Ken L Ho (TSMC), Anil Damle (Cornell), and Lexing Ying (Stanford).