A recursive skeletonization factorization based on strong admissibility

Abstract

We introduce the strong recursive skeletonization factorization (RS-S), a new approximate matrix factorization based on recursive skeletonization for solving discretizations of linear integral equations associated with elliptic partial differential equations in two and three dimensions (and other matrices with similar hierarchical rank structure). Unlike previous skeletonization-based factorizations, RS-S uses a simple modification of skeletonization, strong skeletonization, which compresses only far-field interactions. This leads to an approximate factorization in the form of a product of many block unit-triangular matrices that may be used as a preconditioner or moderate-accuracy direct solver, with dramatically reduced rank growth. We further combine the strong skeletonization procedure with alternating near-field compression to obtain the hybrid recursive skeletonization factorization (RS-WS), a modification of RS-S that exhibits reduced storage cost in many settings. Under suitable rank assumptions both RS-S and RS-WS exhibit linear computational complexity, which we demonstrate with a number of numerical examples.

29 pages, 11 figures

Cited by in corpus (13)

• Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizations
• Fast multipole methods for evaluation of layer potentials with locally-corrected quadratures
• A Hierarchical Butterfly LU Preconditioner for Two-Dimensional Electromagnetic Scattering Problems Involving Open Surfaces
• Asymmetric transport computations in Dirac models of topological insulators
• A fast solver for the narrow capture and narrow escape problems in the sphere
• Linear-Complexity Black-Box Randomized Compression of Rank-Structured Matrices
• Randomized Compression of Rank-Structured Matrices Accelerated with Graph Coloring
• Sparse Hierarchical Preconditioners Using Piecewise Smooth Approximations of Eigenvectors
• A Simplified Fast Multipole Method Based on Strong Recursive Skeletonization
• Randomized Strong Recursive Skeletonization: Simultaneous Compression and LU Factorization of Hierarchical Matrices using Matrix-Vector Products
• Algebraic Inverse Fast Multipole Method: A fast direct solver that is better than HODLR based fast direct solver
• A fast direct solver for two-dimensional transmission problems of elastic waves
• Approximate inversion of discrete Fourier integral operators