A Fast Direct Solver for Structured Linear Systems by Recursive Skeletonization

DOI10.1137/120866683zbMath1259.65062arXiv1110.3105OpenAlexW1990081118MaRDI QIDQ4903729

Publication date: 24 January 2013

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1110.3105

zbMATH Keywords

algorithm numerical experiments boundary integral equation Helmholtz equation factorization ill-conditioned linear systems fast direct solver structured linear systems multilevel matrix compression

Mathematics Subject Classification ID

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) Direct numerical methods for linear systems and matrix inversion (65F05) Boundary element methods for boundary value problems involving PDEs (65N38)

Related Items

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, Overlapping Domain Decomposition Preconditioner for Integral Equations, A fast solver for elastic scattering from axisymmetric objects by boundary integral equations, Existence of $\mathcal {H}$-matrix approximants to the inverses of BEM matrices: The simple-layer operator, 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, A Technique for Updating Hierarchical Skeletonization-Based Factorizations of Integral Operators, Hierarchical Interpolative Factorization for Elliptic Operators: Differential Equations, An accelerated, high-order accurate direct solver for the Lippmann-Schwinger equation for acoustic scattering in the plane, Conformal Mapping via a Density Correspondence for the Double-Layer Potential, 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, ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices, 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, Error analysis of an accelerated interpolative decomposition for 3D Laplace problems, On preconditioners for the Laplace double-layer in 2D, A tensor-train accelerated solver for integral equations in complex geometries, Singular boundary method: a review and computer implementation aspects, Application of the inverse fast multipole method as a preconditioner in a 3D Helmholtz boundary element method, A direct solver for variable coefficient elliptic PDEs discretized via a composite spectral collocation method, FMM-LU: A Fast Direct Solver for Multiscale Boundary Integral Equations in Three Dimensions, Robust integral formulations for electromagnetic scattering from three-dimensional cavities, 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, 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, An adaptive fast multipole accelerated Poisson solver for complex geometries, Preconditioners for Krylov subspace methods: An overview, $\mathcal {H}$-matrix approximability of the inverses of FEM matrices, A fast solver for the narrow capture and narrow escape problems in the sphere, A new fast direct solver for the boundary element method, A neural network warm-start approach for the inverse acoustic obstacle scattering problem, Fast Spatial Gaussian Process Maximum Likelihood Estimation via Skeletonization Factorizations, 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, A fast direct solver for non-intrusive reduced order modeling of vibroacoustic problems, Fast algorithms for integral formulations of steady-state radiative transfer equation, Jump Relations of Certain Hypersingular Stokes Kernels on Regular Surfaces, A Class of Iterative Solvers for the Helmholtz Equation: Factorizations, Sweeping Preconditioners, Source Transfer, Single Layer Potentials, Polarized Traces, and Optimized Schwarz Methods, Second kind integral equation formulation for the modified biharmonic equation and its applications, 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, Analytical Low-Rank Compression via Proxy Point Selection, Hybrid FEM-SBM solver for structural vibration induced underwater acoustic radiation in shallow marine environment, Adaptive Quadrature by Expansion for Layer Potential Evaluation in Two Dimensions, Hierarchical Orthogonal Matrix Generation and Matrix-Vector Multiplications in Rigid Body Simulations, A boundary integral equation approach to computing eigenvalues of the Stokes operator, Sparse Approximate Multifrontal Factorization with Butterfly Compression for High-Frequency Wave Equations, An efficient and highly accurate solver for multi-body acoustic scattering problems involving rotationally symmetric scatterers, Recent advances on the fast multipole accelerated boundary element method for 3D time-harmonic elastodynamics, 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 Solver as a Preconditioner for Dense Linear Systems, Iterative representing set selection for nested cross approximation, A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media, Reconstruction of a compactly supported sound profile in the presence of a random background medium, A heterogeneous FMM for layered media Helmholtz equation. I: Two layers in $\mathbb{R}^2$, Fast multipole preconditioners for sparse matrices arising from elliptic equations, Preconditioners for hierarchical matrices based on their extended sparse form, An $O(N)$ direct solver for integral equations on the plane, An EM-based iterative method for solving large sparse linear systems, Fast Coulomb Matrix Construction via Compressing the Interactions Between Continuous Charge Distributions, Fast, Adaptive, High-Order Accurate Discretization of the Lippmann--Schwinger Equation in Two Dimensions, Hierarchical Interpolative Factorization for Elliptic Operators: Integral Equations, Interpolative Decomposition via Proxy Points for Kernel Matrices, Smoothed Corners and Scattered Waves, ${\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, On the Stability of Some Hierarchical Rank Structured Matrix Algorithms, Fast high-order integral equation methods for solving boundary value problems of two dimensional heat equation in complex geometry, Fast Alternating BiDirectional Preconditioner for the 2D High-Frequency Lippmann--Schwinger Equation, Multifrequency inverse obstacle scattering with unknown impedance boundary conditions using recursive linearization, Efficient Construction of an HSS Preconditioner for Symmetric Positive Definite $\mathcal{H}^2$ Matrices, On the BEM for acoustic wave problems, Sparse Approximate Multifrontal Factorization with Butterfly Compression for High-Frequency Wave Equations, Fast model order reduction boundary element method for large-scale acoustic systems involving surface impedance, Simulation of two-dimensional steady-state heat conduction problems by a fast singular boundary method, Parallel Skeletonization for Integral Equations in Evolving Multiply-Connected Domains, 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, High Resolution Inverse Scattering in Two Dimensions Using Recursive Linearization, A high-order accurate accelerated direct solver for acoustic scattering from surfaces, On the robustness of inverse scattering for penetrable, homogeneous objects with complicated boundary, 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

Uses Software