A fast direct solver for structured linear systems by recursive skeletonization
From MaRDI portal
Publication:4903729
DOI10.1137/120866683zbMATH Open1259.65062arXiv1110.3105OpenAlexW1990081118MaRDI QIDQ4903729FDOQ4903729
Authors: Kenneth L. Ho, Leslie Greengard 
Publication date: 24 January 2013
Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)
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 is the number of discretization points. In our current implementation, the corresponding costs in three dimensions are and for precomputation and solution, respectively. Extensive numerical experiments show a speedup of 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.
Full work available at URL: https://arxiv.org/abs/1110.3105
Recommendations
- A fast direct solver for boundary integral equations in two dimensions
- An \(O(N)\) direct solver for integral equations on the plane
- A fast direct solver for a class of elliptic partial differential equations
- An adaptive fast direct solver for boundary integral equations in two dimensions
- A direct elliptic solver based on hierarchically low-rank Schur complements
algorithmnumerical experimentsfactorizationHelmholtz equationboundary integral equationfast direct solverstructured linear systemsill-conditioned linear systemsmultilevel matrix compression
Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50) Ill-posedness and regularization problems in numerical linear algebra (65F22) Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation (35J05) Boundary element methods for boundary value problems involving PDEs (65N38)
Cited In (95)
- Conformal mapping via a density correspondence for the double-layer potential
- A boundary integral equation approach to computing eigenvalues of the Stokes operator
- Fast high-order integral equation methods for solving boundary value problems of two dimensional heat equation in complex geometry
- FMM-LU: A Fast Direct Solver for Multiscale Boundary Integral Equations in Three Dimensions
- On the BEM for acoustic wave problems
- Interconnected hierarchical structures for fast direct elliptic solution
- Jump relations of certain hypersingular Stokes kernels on regular surfaces
- Fast, adaptive, high-order accurate discretization of the Lippmann-Schwinger equation in two dimensions
- Application of the three‐way decomposition for matrix compression
- Existence of $\mathcal {H}$-matrix approximants to the inverses of BEM matrices: The simple-layer operator
- On preconditioners for the Laplace double-layer in 2D.
- Efficient sum-of-exponentials approximations for the heat kernel and their applications
- Reconstruction of a compactly supported sound profile in the presence of a random background medium
- The inverse fast multipole method: using a fast approximate direct dolver as a preconditioner for dense linear systems
- On a construction of fast direct solvers.
- A recursive skeletonization factorization based on strong admissibility
- Interpolative decomposition via proxy points for kernel matrices
- \(\mathcal {H}\)-matrix approximability of the inverses of FEM matrices
- Efficient mesh deformation based on radial basis function interpolation by means of the inverse fast multipole method
- Hierarchical interpolative factorization for elliptic operators: differential equations
- Hierarchical interpolative factorization for elliptic operators: integral equations
- A heterogeneous FMM for layered media Helmholtz equation. I: Two layers in \(\mathbb{R}^2\)
- Iterative representing set selection for nested cross approximation.
- An FFT-accelerated direct solver for electromagnetic scattering from penetrable axisymmetric objects
- On the stability of some hierarchical rank structured matrix algorithms
- Anatomically accurate high resolution modeling of human whole heart electromechanics: A strongly scalable algebraic multigrid solver method for nonlinear deformation
- Hybrid FEM-SBM solver for structural vibration induced underwater acoustic radiation in shallow marine environment
- Approximate inversion of discrete Fourier integral operators
- A hierarchical matrix approach for computing hydrodynamic interactions
- Robust integral formulations for electromagnetic scattering from three-dimensional cavities
- Simulation of two-dimensional steady-state heat conduction problems by a fast singular boundary method
- Error analysis of an accelerated interpolative decomposition for 3D Laplace problems
- A simplified technique for the efficient and highly accurate discretization of boundary integral equations in 2D on domains with corners
- A direct solver for variable coefficient elliptic PDEs discretized via a composite spectral collocation method
- Fast alternating bidirectional preconditioner for the 2D high-frequency Lippmann-Schwinger equation
- A high-order accurate accelerated direct solver for acoustic scattering from surfaces
- A tensor-train accelerated solver for integral equations in complex geometries
- Parallel Skeletonization for Integral Equations in Evolving Multiply-Connected Domains
- An \(O(N)\) direct solver for integral equations on the plane
- Preconditioners for Krylov subspace methods: An overview
- Second kind integral equation formulation for the modified biharmonic equation and its applications
- High resolution inverse scattering in two dimensions using recursive linearization
- An EM-based iterative method for solving large sparse linear systems
- Fast multipole preconditioners for sparse matrices arising from elliptic equations
- Analytical low-rank compression via proxy point selection
- A fast solver for elastic scattering from axisymmetric objects by boundary integral equations
- Smoothed corners and scattered waves
- Adapting free-space fast multipole method for layered media Green's function: algorithm and analysis
- Recent advances on the fast multipole accelerated boundary element method for 3D time-harmonic elastodynamics
- A fast direct solver for quasi-periodic scattering problems
- A fast direct solver for scattering from periodic structures with multiple material interfaces in two dimensions
- Fast Coulomb matrix construction via compressing the interactions between continuous charge distributions
- A fast block low-rank dense solver with applications to finite-element matrices
- Multifrequency inverse obstacle scattering with unknown impedance boundary conditions using recursive linearization
- A fast direct solver for two dimensional quasi-periodic multilayered media scattering problems
- Application of the inverse fast multipole method as a preconditioner in a 3D Helmholtz boundary element method
- A fast direct singular boundary method for three-dimensional potential problems
- Fast algorithms for integral formulations of steady-state radiative transfer equation
- A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media
- Fast model order reduction boundary element method for large-scale acoustic systems involving surface impedance
- An adaptive fast multipole accelerated Poisson solver for complex geometries
- A technique for updating hierarchical skeletonization-based factorizations of integral operators
- Adaptive quadrature by expansion for layer potential evaluation in two dimensions
- Variants of an explicit kernel-split panel-based Nyström discretization scheme for Helmholtz boundary value problems
- A new fast direct solver for the boundary element method
- \({\mathscr{H}} \)-matrix approximability of inverses of discretizations of the fractional Laplacian
- An \(O(N)\) algorithm for computing expectation of \(N\)-dimensional truncated multi-variate normal distribution. II: computing moments and sparse grid acceleration
- Sparsifying preconditioner for the Lippmann-Schwinger equation
- A class of iterative solvers for the Helmholtz equation: factorizations, sweeping preconditioners, source transfer, single layer potentials, polarized traces, and optimized Schwarz methods
- Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizations
- An efficient and highly accurate solver for multi-body acoustic scattering problems involving rotationally symmetric scatterers
- A fast direct solver for boundary integral equations in two dimensions
- An \(O(N)\) algorithm for computing expectation of \(N\)-dimensional truncated multi-variate normal distribution. I: Fundamentals
- Randomized compression of rank-structured matrices accelerated with graph coloring
- Singular boundary method: a review and computer implementation aspects
- ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices
- Fast multipole methods for the evaluation of layer potentials with locally-corrected quadratures
- On the robustness of inverse scattering for penetrable, homogeneous objects with complicated boundary
- A fast solver for the narrow capture and narrow escape problems in the sphere
- Efficient Construction of an HSS Preconditioner for Symmetric Positive Definite $\mathcal{H}^2$ Matrices
- A neural network warm-start approach for the inverse acoustic obstacle scattering problem
- Random walks in frequency and the reconstruction of obstacles with cavities from multi-frequency data
- An accelerated, high-order accurate direct solver for the Lippmann-Schwinger equation for acoustic scattering in the plane
- Broadband recursive skeletonization
- Preconditioners for hierarchical matrices based on their extended sparse form
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- Hierarchical orthogonal matrix generation and matrix-vector multiplications in rigid body simulations
- A fast direct solver for non-intrusive reduced order modeling of vibroacoustic problems
- Overlapping domain decomposition preconditioner for integral equations
- An efficient high order method for dislocation climb in two dimensions
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- Algebraic inverse fast multipole method: a fast direct solver that is better than HODLR based fast direct solver
- Recent Advances in Acoustic Boundary Element Methods
- Acoustic simulation using singular boundary method based on loop subdivision surfaces: a seamless integration of CAD and CAE
- HODLR\(d\)D: a new black-box fast algorithm for \(N\)-body problems in \(d\)-dimensions with guaranteed error bounds. Applications to integral equations and support vector machines
Uses Software
This page was built for publication: A fast direct solver for structured linear systems by recursive skeletonization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4903729)
