A fast direct solver for structured linear systems by recursive skeletonization

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.

26 pages, 13 figures, 7 tables; accepted by SIAM J Sci Comput

Cited by in corpus (62)

• A Fast Block Low-Rank Dense Solver with Applications to Finite-Element Matrices
• An Immersed Boundary Method for Rigid Bodies
• A recursive skeletonization factorization based on strong admissibility
• An adaptive fast multipole accelerated Poisson solver for complex geometries
• Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizations
• Adaptive quadrature by expansion for layer potential evaluation in two dimensions
• Fast algorithms for integral formulations of steady-state radiative transfer equation
• A fast direct solver for quasi-periodic scattering problems
• H-matrix approximability of the inverses of FEM matrices
• $\mathcal{H}$-matrix approximability of inverses of discretizations of the fractional Laplacian
• The Inverse Fast Multipole Method
• A Neural Network Warm-Start Approach for the Inverse Acoustic Obstacle Scattering Problem
• An FFT-accelerated direct solver for electromagnetic scattering from penetrable axisymmetric objects
• A fast direct solver for scattering from periodic structures with multiple material interfaces in two dimensions
• Inverse Obstacle scattering in two dimensions with multiple frequency data and multiple angles of incidence
• A Heterogeneous FMM for 2-D Layered Media Helmholtz Equation I: Two & Three Layers Cases
• A fast semi-direct least squares algorithm for hierarchically block separable matrices
• Iterative representing set selection for nested cross approximation
• Existence of $\mathcal{H}$-matrix approximants to the inverses of BEM matrices: the simple-layer operator
• Robust integral formulations for electromagnetic scattering from three-dimensional cavities
• A technique for updating hierarchical skeletonization-based factorizations of integral operators
• Fast Multipole Method as a Matrix-Free Hierarchical Low-Rank Approximation
• An O(N) Direct Solver for Integral Equations on the Plane
• Fast multipole methods for evaluation of layer potentials with locally-corrected quadratures
• Fast Multipole Preconditioners for Sparse Matrices Arising from Elliptic Equations
• A fast solver for the narrow capture and narrow escape problems in the sphere
• Conformal Mapping via a Density Correspondence for the Double-Layer Potential
• Linear-Complexity Black-Box Randomized Compression of Rank-Structured Matrices
• On the robustness of inverse scattering for penetrable, homogeneous objects with complicated boundary
• Fast integral equation methods for linear and semilinear heat equations in moving domains
• Randomized Compression of Rank-Structured Matrices Accelerated with Graph Coloring
• A Class of Iterative Solvers for the Helmholtz Equation: Factorizations, Sweeping Preconditioners, Source Transfer, Single Layer Potentials, Polarized Traces, and Optimized Schwarz Methods
• Reconstruction of a compactly supported sound profile in the presence of a random background medium
• A Simplified Fast Multipole Method Based on Strong Recursive Skeletonization
• Inv-ASKIT: A Parallel Fast Diret Solver for Kernel Matrices
• Variants of an explicit kernel-split panel-based Nyström discretization scheme for Helmholtz boundary value problems
• HODLR$d$D: A new Black-box fast algorithm for $N$-body problems in $d$-dimensions with guaranteed error bounds
• An EM based Iterative Method for Solving Large Sparse Linear Systems
• Recursively Preconditioned Hierarchical Interpolative Factorization for Elliptic Partial Differential Equations
• Hierarchical Orthogonal Matrix Generation and Matrix-Vector Multiplications in Rigid Body Simulations
• Adapting free-space fast multipole method for layered media Green's function: algorithm and analysis
• Fast, adaptive, high order accurate discretization of the Lippmann-Schwinger equation in two dimension
• SMASH: Structured matrix approximation by separation and hierarchy
• Error analysis of an accelerated interpolative decomposition for 3D Laplace problems
• A fast direct solver for two dimensional quasi-periodic multilayered media scattering problems
• Graph-Induced Rank Structures and their Representations
• O(N) Hierarchical algorithm for computing the expectations of truncated multi-variate normal distributions in N dimensions
• Randomized Strong Recursive Skeletonization: Simultaneous Compression and LU Factorization of Hierarchical Matrices using Matrix-Vector Products
• A fast direct solver for high frequency scattering from a large cavity in two dimensions
• Algebraic Inverse Fast Multipole Method: A fast direct solver that is better than HODLR based fast direct solver
• A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media
• On preconditioners for the Laplace double-layer in 2D
• Norm-preserving discretization of integral equations for elliptic PDEs with internal layers I: the one-dimensional case
• Efficient construction of an HSS preconditioner for symmetric positive definite ${\mathcal{H}}^2$ matrices
• Approximate inversion of discrete Fourier integral operators
• Sparse Approximate Multifrontal Factorization with Butterfly Compression for High Frequency Wave Equations
• Geometry-Oblivious FMM for Compressing Dense SPD Matrices
• A direct solver with O(N) complexity for variable coefficient elliptic PDEs discretized via a high-order composite spectral collocation method
• Overlapping Domain Decomposition Preconditioner for Integral Equations
• A high-order accurate accelerated direct solver for acoustic scattering from surfaces
• A Fast Direct Solver for Boundary Integral Equations Using Quadrature By Expansion
• Efficient sum-of-exponentials approximations for the heat kernel and their applications