Hierarchical interpolative factorization for elliptic operators: differential equations
From MaRDI portal
Abstract: This paper introduces the hierarchical interpolative factorization for elliptic partial differential equations (HIF-DE) in two (2D) and three dimensions (3D). This factorization takes the form of an approximate generalized LU/LDL decomposition that facilitates the efficient inversion of the discretized operator. HIF-DE is based on the multifrontal method but uses skeletonization on the separator fronts to sparsify the dense frontal matrices and thus reduce the cost. We conjecture that this strategy yields linear complexity in 2D and quasilinear complexity in 3D. Estimated linear complexity in 3D can be achieved by skeletonizing the compressed fronts themselves, which amounts geometrically to a recursive dimensional reduction scheme. Numerical experiments support our claims and further demonstrate the performance of our algorithm as a fast direct solver and preconditioner. MATLAB codes are freely available.
Recommendations
- Hierarchical interpolative factorization for elliptic operators: integral equations
- Recursively preconditioned hierarchical interpolative factorization for elliptic partial differential equations
- Distributed-memory hierarchical interpolative factorization
- A fast nested dissection solver for Cartesian 3D elliptic problems using hierarchical matrices
- Why Finite Element Discretizations Can Be Factored by Triangular Hierarchical Matrices
Cites work
- scientific article; zbMATH DE number 1069612 (Why is no real title available?)
- scientific article; zbMATH DE number 1953444 (Why is no real title available?)
- A direct solver with O(N) complexity for integral equations on one-dimensional domains
- A direct solver with O(N) complexity for variable coefficient elliptic PDEs discretized via a high-order composite spectral collocation method
- A fast algorithm for particle simulations
- A fast block low-rank dense solver with applications to finite-element matrices
- A fast direct solver for a class of elliptic partial differential equations
- A fast direct solver for boundary integral equations in two dimensions
- A fast direct solver for elliptic problems on general meshes in 2D
- A fast direct solver for structured linear systems by recursive skeletonization
- A fast directional algorithm for high frequency acoustic scattering in two dimensions
- A fast nested dissection solver for Cartesian 3D elliptic problems using hierarchical matrices
- 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 O(N) algorithm for constructing the solution operator to 2D elliptic boundary value problems in the absence of body loads
- Approximation of solution operators of elliptic partial differential equations by \({\mathcal H}\)- and \({\mathcal H}^2\)-matrices
- 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
- Domain decomposition based \({\mathcal H}\)-LU preconditioning
- Efficient inversion of the Galerkin matrix of general second-order elliptic operators with nonsmooth coefficients
- 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 Directional Multilevel Algorithms for Oscillatory Kernels
- Fast algorithms for hierarchically semiseparable matrices
- Fast direct solvers for integral equations in complex three-dimensional domains
- 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: integral equations
- Iterative Methods by Space Decomposition and Subspace Correction
- Methods of conjugate gradients for solving linear systems
- Multi-Level Adaptive Solutions to Boundary-Value Problems
- Nested Dissection of a Regular Finite Element Mesh
- On the Compression of Low Rank Matrices
- On the numerical rank of the off-diagonal blocks of Schur complements of discretized elliptic PDEs
- Randomized sparse direct solvers
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- The Multifrontal Method for Sparse Matrix Solution: Theory and Practice
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
Cited in
(54)- An O(N) algorithm for computing expectation of N-dimensional truncated multi-variate normal distribution. I: Fundamentals
- Hierarchical orthogonal factorization: sparse least squares problems
- Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizations
- Recursively preconditioned hierarchical interpolative factorization for elliptic partial differential equations
- Sparse hierarchical solvers with guaranteed convergence
- Gamblets for opening the complexity-bottleneck of implicit schemes for hyperbolic and parabolic ODEs/PDEs with rough coefficients
- Distributed-memory hierarchical interpolative factorization
- Interconnected hierarchical structures for fast direct elliptic solution
- 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
- Hierarchical interpolative factorization for self Green's function in 3D modified Poisson-Boltzmann equations
- On the complexity of the block low-rank multifrontal factorization
- A multilevel approach for trace system in HDG discretizations
- 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
- A robust hierarchical solver for ill-conditioned systems with applications to ice sheet modeling
- Hierarchical interpolative factorization for elliptic operators: integral equations
- Hybrid FEM-SBM solver for structural vibration induced underwater acoustic radiation in shallow marine environment
- Linear-scaling selected inversion based on hierarchical interpolative factorization for self Green's function for modified Poisson-Boltzmann equation in two dimensions
- Fast alternating bidirectional preconditioner for the 2D high-frequency Lippmann-Schwinger equation
- Second‐order accurate hierarchical approximate factorizations for solving sparse linear systems
- Hierarchical interpolative factorization preconditioner for parabolic equations
- A fast direct solver for boundary integral equations using quadrature by expansion
- RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems
- Parallel Skeletonization for Integral Equations in Evolving Multiply-Connected Domains
- Intrinsic Complexity and Scaling Laws: From Random Fields to Random Vectors
- Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation
- Sparse Hierarchical Preconditioners Using Piecewise Smooth Approximations of Eigenvectors
- A data scalable augmented Lagrangian KKT preconditioner for large-scale inverse problems
- Separability of the kernel function in an integral formulation for the anisotropic radiative transfer equation
- An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
- Emulation of higher-order tensors in manifold Monte Carlo methods for Bayesian inverse problems
- Variational training of neural network approximations of solution maps for physical models
- A fast nested dissection solver for Cartesian 3D elliptic problems using hierarchical matrices
- Hierarchical Bases for Elliptic Problems
- Recursive sparse LU decomposition based on nested dissection and low rank approximations
- Application of the inverse fast multipole method as a preconditioner in a 3D Helmholtz boundary element method
- Fast algorithms for integral formulations of steady-state radiative transfer equation
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- Likelihood approximation with hierarchical matrices for large spatial datasets
- Parallelization of the inverse fast multipole method with an application to boundary element method
- An efficient high order method for dislocation climb in two dimensions
- Continuous Cross Approximation of Matrices Arising Out of Kernel Functions
- A technique for updating hierarchical skeletonization-based factorizations of integral operators
- A fast direct solver for nonlocal operators in wavelet coordinates
- \({\mathscr{H}} \)-matrix approximability of inverses of discretizations of the fractional Laplacian
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- 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
- Distributed-memory \(\mathcal{H}\)-matrix algebra. I: Data distribution and matrix-vector multiplication
- Why Finite Element Discretizations Can Be Factored by Triangular Hierarchical Matrices
This page was built for publication: Hierarchical interpolative factorization for elliptic operators: differential equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3185925)
