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
- 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 algorithms for hierarchically semiseparable matrices
- Fast direct solvers for integral equations in complex three-dimensional domains
- Fast Directional Multilevel Algorithms for Oscillatory Kernels
- 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
- scientific article; zbMATH DE number 1069612 (Why is no real title available?)
- scientific article; zbMATH DE number 1953444 (Why is no real title available?)
- 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
(56)- Application of the inverse fast multipole method as a preconditioner in a 3D Helmholtz boundary element method
- Recursively preconditioned hierarchical interpolative factorization for elliptic partial differential equations
- 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 multilevel approach for trace system in HDG discretizations
- A fast direct solver for nonlocal operators in wavelet coordinates
- Linear-scaling selected inversion based on hierarchical interpolative factorization for self Green's function for modified Poisson-Boltzmann equation in two dimensions
- Hierarchical orthogonal factorization: sparse least squares problems
- Fast algorithms for integral formulations of steady-state radiative transfer equation
- Hierarchical interpolative factorization preconditioner for parabolic equations
- A robust hierarchical solver for ill-conditioned systems with applications to ice sheet modeling
- 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
- \({\mathscr{H}} \)-matrix approximability of inverses of discretizations of the fractional Laplacian
- Distributed-memory hierarchical interpolative factorization
- Likelihood approximation with hierarchical matrices for large spatial datasets
- Parallelization of the inverse fast multipole method with an application to boundary element method
- Fast, adaptive, high-order accurate discretization of the Lippmann-Schwinger equation in two dimensions
- Hierarchical interpolative factorization for elliptic operators: integral equations
- Fast alternating bidirectional preconditioner for the 2D high-frequency Lippmann-Schwinger equation
- 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 nested dissection solver for Cartesian 3D elliptic problems using hierarchical matrices
- Why Finite Element Discretizations Can Be Factored by Triangular Hierarchical Matrices
- Hierarchical Bases for Elliptic Problems
- ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices
- Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizations
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- Parallel Skeletonization for Integral Equations in Evolving Multiply-Connected Domains
- RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems
- An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
- Sparse Hierarchical Preconditioners Using Piecewise Smooth Approximations of Eigenvectors
- Separability of the kernel function in an integral formulation for the anisotropic radiative transfer equation
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- Intrinsic Complexity and Scaling Laws: From Random Fields to Random Vectors
- On the complexity of the block low-rank multifrontal factorization
- A data scalable augmented Lagrangian KKT preconditioner for large-scale inverse problems
- 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
- Singular boundary method: a review and computer implementation aspects
- Second‐order accurate hierarchical approximate factorizations for solving sparse linear systems
- Sparse hierarchical solvers with guaranteed convergence
- Acoustic simulation using singular boundary method based on loop subdivision surfaces: a seamless integration of CAD and CAE
- Gamblets for opening the complexity-bottleneck of implicit schemes for hyperbolic and parabolic ODEs/PDEs with rough coefficients
- A fast direct solver for boundary integral equations using quadrature by expansion
- Recursive sparse LU decomposition based on nested dissection and low rank approximations
- Distributed-memory \(\mathcal{H}\)-matrix algebra. I: Data distribution and matrix-vector multiplication
- Hierarchical interpolative factorization for self Green's function in 3D modified Poisson-Boltzmann equations
- Continuous Cross Approximation of Matrices Arising Out of Kernel Functions
- A unified framework for multiscale spectral generalized FEMs and low-rank approximations to multiscale PDEs
- Emulation of higher-order tensors in manifold Monte Carlo methods for Bayesian inverse problems
- LoCCA: Localized Chebyshev Cross Approximation for Kernel Matrix Factorization via Nodal Perturbation Stability
- Variational training of neural network approximations of solution maps for physical models
- \(\mathcal {H}\)-matrix approximability of the inverses of FEM 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)
