A fast direct solver for structured linear systems by recursive skeletonization
From MaRDI portal
Publication:4903729
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)
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.
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
Cited in
(95)- A fast direct solver for boundary integral equations in two dimensions
- Sparsifying preconditioner for the Lippmann-Schwinger equation
- An O(N) algorithm for computing expectation of N-dimensional truncated multi-variate normal distribution. I: Fundamentals
- 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
- A boundary integral equation approach to computing eigenvalues of the Stokes operator
- 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
- Conformal mapping via a density correspondence for the double-layer potential
- Fast high-order integral equation methods for solving boundary value problems of two dimensional heat equation in complex geometry
- On the BEM for acoustic wave problems
- Interconnected hierarchical structures for fast direct elliptic solution
- FMM-LU: A Fast Direct Solver for Multiscale Boundary Integral Equations in Three Dimensions
- Jump relations of certain hypersingular Stokes kernels on regular surfaces
- Fast, adaptive, high-order accurate discretization of the Lippmann-Schwinger equation in two dimensions
- Existence of $\mathcal {H}$-matrix approximants to the inverses of BEM matrices: The simple-layer operator
- Application of the three‐way decomposition for matrix compression
- Randomized compression of rank-structured matrices accelerated with graph coloring
- Efficient sum-of-exponentials approximations for the heat kernel and their applications
- On preconditioners for the Laplace double-layer in 2D.
- On a construction of fast direct solvers.
- 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
- \(\mathcal {H}\)-matrix approximability of the inverses of FEM matrices
- ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices
- Singular boundary method: a review and computer implementation aspects
- A recursive skeletonization factorization based on strong admissibility
- Efficient mesh deformation based on radial basis function interpolation by means of the inverse fast multipole method
- Interpolative decomposition via proxy points for kernel matrices
- A heterogeneous FMM for layered media Helmholtz equation. I: Two layers in \(\mathbb{R}^2\)
- Hierarchical interpolative factorization for elliptic operators: differential equations
- Fast multipole methods for the evaluation of layer potentials with locally-corrected quadratures
- Hierarchical interpolative factorization for elliptic operators: integral equations
- On the robustness of inverse scattering for penetrable, homogeneous objects with complicated boundary
- An FFT-accelerated direct solver for electromagnetic scattering from penetrable axisymmetric objects
- 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
- On the stability of some hierarchical rank structured matrix algorithms
- Robust integral formulations for electromagnetic scattering from three-dimensional cavities
- Approximate inversion of discrete Fourier integral operators
- A hierarchical matrix approach for computing hydrodynamic interactions
- Simulation of two-dimensional steady-state heat conduction problems by a fast singular boundary method
- Iterative representing set selection for nested cross approximation.
- 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 fast solver for the narrow capture and narrow escape problems in the sphere
- A direct solver for variable coefficient elliptic PDEs discretized via a composite spectral collocation method
- Efficient Construction of an HSS Preconditioner for Symmetric Positive Definite $\mathcal{H}^2$ Matrices
- 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
- 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
- Parallel Skeletonization for Integral Equations in Evolving Multiply-Connected Domains
- Second kind integral equation formulation for the modified biharmonic equation and its applications
- Broadband recursive skeletonization
- Preconditioners for hierarchical matrices based on their extended sparse form
- An \(O(N)\) direct solver for integral equations on the plane
- Preconditioners for Krylov subspace methods: An overview
- Fast multipole preconditioners for sparse matrices arising from elliptic equations
- High resolution inverse scattering in two dimensions using recursive linearization
- An EM-based iterative method for solving large sparse linear systems
- A fast solver for elastic scattering from axisymmetric objects by boundary integral equations
- Analytical low-rank compression via proxy point selection
- 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
- 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
- Fast Coulomb matrix construction via compressing the interactions between continuous charge distributions
- 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
- Hierarchical orthogonal matrix generation and matrix-vector multiplications in rigid body simulations
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media
- A fast direct solver for non-intrusive reduced order modeling of vibroacoustic problems
- Fast model order reduction boundary element method for large-scale acoustic systems involving surface impedance
- Overlapping domain decomposition preconditioner for integral equations
- An adaptive fast multipole accelerated Poisson solver for complex geometries
- An efficient high order method for dislocation climb in two dimensions
- A technique for updating hierarchical skeletonization-based factorizations of integral operators
- 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
- Adaptive quadrature by expansion for layer potential evaluation in two dimensions
- \({\mathscr{H}} \)-matrix approximability of inverses of discretizations of the fractional Laplacian
- 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
- An \(O(N)\) algorithm for computing expectation of \(N\)-dimensional truncated multi-variate normal distribution. II: computing moments and sparse grid acceleration
- Acoustic simulation using singular boundary method based on loop subdivision surfaces: a seamless integration of CAD and CAE
- An efficient and highly accurate solver for multi-body acoustic scattering problems involving rotationally symmetric scatterers
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)
