The Inverse Fast Multipole Method

Abstract

This article introduces a new fast direct solver for linear systems arising out of wide range of applications, integral equations, multivariate statistics, radial basis interpolation, etc., to name a few. \emph{The highlight of this new fast direct solver is that the solver scales linearly in the number of unknowns in all dimensions.} The solver, termed as Inverse Fast Multipole Method (abbreviated as IFMM), works on the same data-structure as the Fast Multipole Method (abbreviated as FMM). More generally, the solver can be immediately extended to the class of hierarchical matrices, denoted as ${\mathcal{H}}^2$ matrices with strong admissibility criteria (weak low-rank structure), i.e., \emph{the interaction between neighboring cluster of particles is full-rank whereas the interaction between particles corresponding to well-separated clusters can be efficiently represented as a low-rank matrix}. The algorithm departs from existing approaches in the fact that throughout the algorithm the interaction corresponding to neighboring clusters are always treated as full-rank interactions. Our approach relies on two major ideas: (i) The $N\times N$ matrix arising out of FMM (from now on termed as FMM matrix) can be represented as an extended sparser matrix of size $M\times M$, where $M\approx 3N$. (ii) While solving the larger extended sparser matrix, \emph{the fill-in's that arise in the matrix blocks corresponding to well-separated clusters are hierarchically compressed}. The ordering of the equations and the unknowns in the extended sparser matrix is strongly related to the local and multipole coefficients in the FMM~\cite{greengard1987fast} and \emph{the order of elimination is different from the usual nested dissection approach}. Numerical benchmarks on $2$D manifold confirm the linear scaling of the algorithm.

25 pages, 28 figures

References in corpus (3)

• A fast direct solver for structured linear systems by recursive skeletonization
• A Fast Block Low-Rank Dense Solver with Applications to Finite-Element Matrices
• Fast symmetric factorization of hierarchical matrices with applications

Cited by in corpus (12)

• A Fast Block Low-Rank Dense Solver with Applications to Finite-Element Matrices
• Immersed Boundary Smooth Extension: A high-order method for solving PDE on arbitrary smooth domains using Fourier spectral methods
• Accuracy Directly Controlled Fast Direct Solutions of General ${\mathcal{H}}^2$-Matrices and Its Application to Electrically Large Integral-Equation-Based Electromagnetic Analysis
• Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation
• Fast symmetric factorization of hierarchical matrices with applications
• Fast Multipole Method as a Matrix-Free Hierarchical Low-Rank Approximation
• Parallelization of the inverse fast multipole method with an application to boundary element method
• An efficient preconditioner for the fast simulation of a 2D Stokes flow in porous media
• A Fast and Memory Efficient Sparse Solver with Applications to Finite-Element Matrices
• Graph-Induced Rank Structures and their Representations
• Efficient construction of an HSS preconditioner for symmetric positive definite ${\mathcal{H}}^2$ matrices
• A fast direct solver for the advection-diffusion equation using low-rank approximation of the Green's function