A fast direct solver for structured linear systems by recursive skeletonization
From MaRDI portal
Publication:4903729
algorithmboundary integral equationfactorizationfast direct solverHelmholtz equationill-conditioned linear systemsmultilevel matrix compressionnumerical experimentsstructured linear systems
Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation (35J05) Direct numerical methods for linear systems and matrix inversion (65F05) Ill-posedness and regularization problems in numerical linear algebra (65F22) Computational methods for sparse matrices (65F50) 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
(only showing first 100 items - show all)- A tensor-train accelerated solver for integral equations in complex geometries
- Application of the inverse fast multipole method as a preconditioner in a 3D Helmholtz boundary element method
- Robust integral formulations for electromagnetic scattering from three-dimensional cavities
- An adaptive fast multipole accelerated Poisson solver for complex geometries
- A new fast direct solver for the boundary element method
- Recent advances on the fast multipole accelerated boundary element method for 3D time-harmonic elastodynamics
- A fast direct solver for boundary integral equations in two dimensions
- Fast multipole preconditioners for sparse matrices arising from elliptic equations
- A boundary integral equation approach to computing eigenvalues of the Stokes operator
- Multifrequency inverse obstacle scattering with unknown impedance boundary conditions using recursive linearization
- Fast model order reduction boundary element method for large-scale acoustic systems involving surface impedance
- An \(O(N)\) algorithm for computing expectation of \(N\)-dimensional truncated multi-variate normal distribution. II: computing moments and sparse grid acceleration
- Interconnected hierarchical structures for fast direct elliptic solution
- A fast direct singular boundary method for three-dimensional potential problems
- Approximate inversion of discrete Fourier integral operators
- A hierarchical matrix approach for computing hydrodynamic interactions
- A fast solver for elastic scattering from axisymmetric objects by boundary integral equations
- An accelerated, high-order accurate direct solver for the Lippmann-Schwinger equation for acoustic scattering in the plane
- Error analysis of an accelerated interpolative decomposition for 3D Laplace problems
- Fast algorithms for integral formulations of steady-state radiative transfer equation
- An FFT-accelerated direct solver for electromagnetic scattering from penetrable axisymmetric objects
- An O(N) algorithm for computing expectation of N-dimensional truncated multi-variate normal distribution. I: Fundamentals
- Hybrid FEM-SBM solver for structural vibration induced underwater acoustic radiation in shallow marine environment
- A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media
- \({\mathscr{H}} \)-matrix approximability of inverses of discretizations of the fractional Laplacian
- Efficient mesh deformation based on radial basis function interpolation by means of the inverse fast multipole method
- 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
- Simulation of two-dimensional steady-state heat conduction problems by a fast singular boundary method
- A high-order accurate accelerated direct solver for acoustic scattering from surfaces
- Efficient sum-of-exponentials approximations for the heat kernel and their applications
- Variants of an explicit kernel-split panel-based Nyström discretization scheme for Helmholtz boundary value problems
- A fast block low-rank dense solver with applications to finite-element matrices
- Anatomically accurate high resolution modeling of human whole heart electromechanics: A strongly scalable algebraic multigrid solver method for nonlinear deformation
- An \(O(N)\) direct solver for integral equations on the plane
- Adapting free-space fast multipole method for layered media Green's function: algorithm and analysis
- A fast direct solver for two dimensional quasi-periodic multilayered media scattering problems
- A fast direct solver for non-intrusive reduced order modeling of vibroacoustic problems
- Fast, adaptive, high-order accurate discretization of the Lippmann-Schwinger equation in two dimensions
- Hierarchical interpolative factorization for elliptic operators: integral equations
- Smoothed corners and scattered waves
- On the stability of some hierarchical rank structured matrix algorithms
- Fast alternating bidirectional preconditioner for the 2D high-frequency Lippmann-Schwinger equation
- On preconditioners for the Laplace double-layer in 2D.
- Hierarchical interpolative factorization for elliptic operators: differential equations
- Existence of $\mathcal {H}$-matrix approximants to the inverses of BEM matrices: The simple-layer operator
- A technique for updating hierarchical skeletonization-based factorizations of integral operators
- A fast direct solver for quasi-periodic scattering problems
- A simplified technique for the efficient and highly accurate discretization of boundary integral equations in 2D on domains with corners
- A fast direct solver for scattering from periodic structures with multiple material interfaces in two dimensions
- A direct solver for variable coefficient elliptic PDEs discretized via a composite spectral collocation method
- Conformal mapping via a density correspondence for the double-layer potential
- ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices
- Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizations
- A class of iterative solvers for the Helmholtz equation: factorizations, sweeping preconditioners, source transfer, single layer potentials, polarized traces, and optimized Schwarz methods
- Adaptive quadrature by expansion for layer potential evaluation in two dimensions
- Hierarchical orthogonal matrix generation and matrix-vector multiplications in rigid body simulations
- Second kind integral equation formulation for the modified biharmonic equation and its applications
- Reconstruction of a compactly supported sound profile in the presence of a random background medium
- Efficient Construction of an HSS Preconditioner for Symmetric Positive Definite $\mathcal{H}^2$ Matrices
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- Parallel Skeletonization for Integral Equations in Evolving Multiply-Connected Domains
- Overlapping domain decomposition preconditioner for integral equations
- Jump relations of certain hypersingular Stokes kernels on regular surfaces
- Analytical low-rank compression via proxy point selection
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- An EM-based iterative method for solving large sparse linear systems
- Fast Coulomb matrix construction via compressing the interactions between continuous charge distributions
- Interpolative decomposition via proxy points for kernel matrices
- An efficient and highly accurate solver for multi-body acoustic scattering problems involving rotationally symmetric scatterers
- Sparsifying preconditioner for the Lippmann-Schwinger equation
- High resolution inverse scattering in two dimensions using recursive linearization
- Application of the three‐way decomposition for matrix compression
- An efficient high order method for dislocation climb in two dimensions
- A recursive skeletonization factorization based on strong admissibility
- The inverse fast multipole method: using a fast approximate direct dolver as a preconditioner for dense linear systems
- Iterative representing set selection for nested cross approximation.
- On the robustness of inverse scattering for penetrable, homogeneous objects with complicated boundary
- Preconditioners for hierarchical matrices based on their extended sparse form
- Singular boundary method: a review and computer implementation aspects
- FMM-LU: A Fast Direct Solver for Multiscale Boundary Integral Equations in Three Dimensions
- 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
- HODLRdD: 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
- Preconditioners for Krylov subspace methods: An overview
- A fast solver for the narrow capture and narrow escape problems in the sphere
- 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
- Fast multipole methods for the evaluation of layer potentials with locally-corrected quadratures
- Acoustic simulation using singular boundary method based on loop subdivision surfaces: a seamless integration of CAD and CAE
- Randomized compression of rank-structured matrices accelerated with graph coloring
- Broadband recursive skeletonization
- A fast direct solver for boundary integral equations using quadrature by expansion
- Hardware acceleration for HPS algorithms in two and three dimensions
- Estimating a matrix's singular values with interpolative decompositions
- Robust blockwise random pivoting: fast and accurate adaptive interpolative decomposition
- A fast approach evaluating origin intensity factors on Neumann boundary in the singular boundary method
- A dual-space multilevel kernel-splitting framework for discrete and continuous convolution
- A simplified fast multipole method based on strong recursive skeletonization
- Complex scaling for the Helmholtz equation with Dirichlet boundary conditions in a perturbed half-space
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)
