Hierarchical interpolative factorization for elliptic operators: integral equations
From MaRDI portal
Abstract: This paper introduces the hierarchical interpolative factorization for integral equations (HIF-IE) associated with elliptic problems in two and three dimensions. This factorization takes the form of an approximate generalized LU decomposition that permits the efficient application of the discretized operator and its inverse. HIF-IE is based on the recursive skeletonization algorithm but incorporates a novel combination of two key features: (1) a matrix factorization framework for sparsifying structured dense matrices and (2) a recursive dimensional reduction strategy to decrease the cost. Thus, higher-dimensional problems are effectively mapped to one dimension, and we conjecture that constructing, applying, and inverting the factorization all have linear or quasilinear complexity. Numerical experiments support this claim and further demonstrate the performance of our algorithm as a generalized fast multipole method, direct solver, and preconditioner. HIF-IE is compatible with geometric adaptivity and can handle both boundary and volume problems. MATLAB codes are freely available.
The authors study the methods to approximate solving the integral equation NEWLINE\[NEWLINE a(x) u(x)+ b(x)\int_{\Omega}K(\|x-y\|u(y)d\Omega (y)=f(x),\qquad x\in \Omega \subset \mathbb R^{d},NEWLINE\]NEWLINE derived from the boundary value problem NEWLINE\[NEWLINE \nabla ( a(x) \nabla u(x)) = f(x) \qquad x\in \Omega\subset \mathbb R^{d}, \,d= 2,3 NEWLINE\]NEWLINE Discretization of the integral equation, using the different approximate schemes (collocation, Galerkin method and other), leads to a system of linear equations NEWLINE\[NEWLINE Ax = f, \qquad A \in C^{N\times N}.NEWLINE\]NEWLINE The main idea of this paper is to construct algorithms which permit to obtain the matrix \(A\) in factorized form \(A= LV\) or \(A=LDV\). Also an analysis of the complexity of the constructed algorithms and the numerical results for three concrete examples are given.
Recommendations
- Hierarchical interpolative factorization for elliptic operators: differential equations
- Recursively preconditioned hierarchical interpolative factorization for elliptic partial differential equations
- Overlapping domain decomposition preconditioner for integral equations
- An \(O(N)\) direct solver for integral equations on the plane
- A fast direct solver for structured linear systems by recursive skeletonization
Cites work
- A direct solver with O(N) complexity for integral equations on one-dimensional domains
- A Fast ULV Decomposition Solver for Hierarchically Semiseparable Representations
- A fast algorithm for particle simulations
- A fast direct solver for boundary integral equations in two dimensions
- A fast direct solver for structured linear systems by recursive skeletonization
- A fast direct solver for the integral equations of scattering theory on planar curves with corners
- A fast directional algorithm for high frequency acoustic scattering in two dimensions
- A fast semidirect least squares algorithm for hierarchically block separable matrices
- A Fast Solver for HSS Representations via Sparse Matrices
- A fast summation tree code for Matérn kernel
- A fast, direct algorithm for the Lippmann-Schwinger integral equation in two dimensions
- A kernel-independent adaptive fast multipole algorithm in two and three dimensions
- A sparse \({\mathcal H}\)-matrix arithmetic. II: Application to multi-dimensional problems
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- A superfast structured solver for Toeplitz linear systems via randomized sampling
- An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation
- An O(N) algorithm for constructing the solution operator to 2D elliptic boundary value problems in the absence of body loads
- An \(O(N)\) direct solver for integral equations on the plane
- An Accelerated Kernel-Independent Fast Multipole Method in One Dimension
- Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems
- Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Efficient structured multifrontal factorization for general large sparse matrices
- Estimating Extremal Eigenvalues and Condition Numbers of Matrices
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Existence of H-matrix approximants to the inverse FE-matrix of elliptic operators with L^-coefficients
- Fast algorithms for hierarchically semiseparable matrices
- Fast direct solvers for integral equations in complex three-dimensional domains
- Fast Directional Multilevel Algorithms for Oscillatory Kernels
- Fast wavelet transforms and numerical algorithms I
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- Hierarchical interpolative factorization for elliptic operators: differential equations
- scientific article; zbMATH DE number 1069612 (Why is no real title available?)
- scientific article; zbMATH DE number 2221668 (Why is no real title available?)
- Methods of conjugate gradients for solving linear systems
- Nested Dissection of a Regular Finite Element Mesh
- On interpolation and integration in finite-dimensional spaces of bounded functions
- On the Compression of Low Rank Matrices
- On the fast matrix multiplication in the boundary element method by panel clustering
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- The black-box fast multipole method
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
- Wavelet-Like Bases for the Fast Solution of Second-Kind Integral Equations
Cited in
(55)- A tensor-train accelerated solver for integral equations in complex geometries
- A fast direct solver for boundary value problems on locally perturbed geometries
- Algorithms for inversion of diagonal plus semiseparable operator matrices
- Recursively preconditioned hierarchical interpolative factorization for elliptic partial differential equations
- A fast direct solver for integral equations on locally refined boundary discretizations and its application to multiphase flow simulations
- All-at-once method for variable-order time fractional diffusion equations
- Approximate inversion of discrete Fourier integral operators
- A fast multipole method for Fredholm integral equations of the second kind with general kernel \(K(x,y)=K(x-y)\)
- Hierarchical orthogonal factorization: sparse least squares problems
- An accelerated, high-order accurate direct solver for the Lippmann-Schwinger equation for acoustic scattering in the plane
- Fast algorithms for integral formulations of steady-state radiative transfer equation
- Hierarchical interpolative factorization preconditioner for parabolic equations
- An O(N) algorithm for computing expectation of N-dimensional truncated multi-variate normal distribution. I: Fundamentals
- \({\mathscr{H}} \)-matrix approximability of inverses of discretizations of the fractional Laplacian
- Adaptive finite element method for fractional differential equations using hierarchical matrices
- Fast high-order integral equation methods for solving boundary value problems of two dimensional heat equation in complex geometry
- Distributed-memory hierarchical interpolative factorization
- A fast direct solver for two dimensional quasi-periodic multilayered media scattering problems
- Coarse-proxy reduced basis methods for integral equations
- Fast, adaptive, high-order accurate discretization of the Lippmann-Schwinger equation in two dimensions
- 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
- ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices
- Efficient Construction of an HSS Preconditioner for Symmetric Positive Definite $\mathcal{H}^2$ Matrices
- Sparse Cholesky Factorization by Kullback--Leibler Minimization
- Parallel Skeletonization for Integral Equations in Evolving Multiply-Connected Domains
- Hierarchical orthogonal factorization: sparse square matrices
- Overlapping domain decomposition preconditioner for integral equations
- Fast Low-Rank Kernel Matrix Factorization Using Skeletonized Interpolation
- Sparsifying preconditioner for the Lippmann-Schwinger equation
- Directional preconditioner for 2D high frequency obstacle scattering
- 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
- Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation
- FMM-LU: A Fast Direct Solver for Multiscale Boundary Integral Equations in Three Dimensions
- Linear-Cost Covariance Functions for Gaussian Random Fields
- Sparse hierarchical solvers with guaranteed convergence
- Broadband recursive skeletonization
- Sparse inverse Cholesky factorization of dense kernel matrices by greedy conditional selection
- The Helmholtz Dirichlet and Neumann problems on piecewise smooth open curves
- Robust blockwise random pivoting: fast and accurate adaptive interpolative decomposition
- Distributed-memory \(\mathcal{H}\)-matrix algebra. I: Data distribution and matrix-vector multiplication
- Multi-layer hierarchical structures
- Hierarchical interpolative factorization for self Green's function in 3D modified Poisson-Boltzmann equations
- A simplified fast multipole method based on strong recursive skeletonization
- Sparse Cholesky factorization for solving nonlinear PDEs via Gaussian processes
- Compact Rational Krylov for Parametrized Systems with Application to BEM Frequency Sweeping
- Truncated kernel stochastic gradient descent on spheres
- Emulation of higher-order tensors in manifold Monte Carlo methods for Bayesian inverse problems
- Estimating Hierarchically Rank Structured Covariance Matrices
- Hierarchical low-rank compression exploiting symmetric boundary integral equations in transmission scattering
- Variational training of neural network approximations of solution maps for physical models
- Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity
This page was built for publication: Hierarchical interpolative factorization for elliptic operators: integral equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2812291)
