Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation
From MaRDI portal
Abstract: Inversion of sparse matrices with standard direct solve schemes is robust, but computationally expensive. Iterative solvers, on the other hand, demonstrate better scalability; but, need to be used with an appropriate preconditioner (e.g., ILU, AMG, Gauss-Seidel, etc.) for proper convergence. The choice of an effective preconditioner is highly problem dependent. We propose a novel fully algebraic sparse matrix solve algorithm, which has linear complexity with the problem size. Our scheme is based on the Gauss elimination. For a given matrix, we approximate the LU factorization with a tunable accuracy determined a priori. This method can be used as a stand-alone direct solver with linear complexity and tunable accuracy, or it can be used as a black-box preconditioner in conjunction with iterative methods such as GMRES. The proposed solver is based on the low-rank approximation of fill-ins generated during the elimination. Similar to H-matrices, fill-ins corresponding to blocks that are well-separated in the adjacency graph are represented via a hierarchical structure. The linear complexity of the algorithm is guaranteed if the blocks corresponding to well-separated clusters of variables are numerically low-rank.
Recommendations
- An algebraic multilevel preconditioner with low-rank corrections for sparse symmetric matrices
- Randomized sparse direct solvers
- A fast, memory efficient and robust sparse preconditioner based on a multifrontal approach with applications to finite-element matrices
- An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
- The inverse fast multipole method: using a fast approximate direct dolver as a preconditioner for dense linear systems
Cites work
- H^2-matrix approximation of integral operators by interpolation
- A Block Algorithm for Matrix 1-Norm Estimation, with an Application to 1-Norm Pseudospectra
- 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 ULV Decomposition Solver for Hierarchically Semiseparable Representations
- A fast algorithm for particle simulations
- A fast block low-rank dense solver with applications to finite-element matrices
- A Fast Solver for HSS Representations via Sparse Matrices
- A FETI-preconditioned conjugate gradient method for large-scale stochastic finite element problems
- A generalization of the fast LUP matrix decomposition algorithm and applications
- A kernel-independent adaptive fast multipole algorithm in two and three dimensions
- A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices
- A review of algebraic multigrid
- A sparse \({\mathcal H}\)-matrix arithmetic: General complexity estimates
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- Adaptive low-rank approximation of collocation matrices
- Algebraic multigrid theory: The symmetric case
- 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)\) direct solver for integral equations on the plane
- An adaptive fast direct solver for boundary integral equations in two dimensions
- An algebraic multifrontal preconditioner that exploits the low-rank property.
- Computing the Minimum Fill-In is NP-Complete
- Condition Estimates
- Direct Methods for Sparse Linear Systems
- Divide and conquer low-rank preconditioners for symmetric matrices
- 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
- Generalized Nested Dissection
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- Hierarchical interpolative factorization for elliptic operators: differential equations
- Hierarchical interpolative factorization for elliptic operators: integral equations
- Hierarchical matrices. A means to efficiently solve elliptic boundary value problems
- scientific article; zbMATH DE number 3874483 (Why is no real title available?)
- ILUT: A dual threshold incomplete LU factorization
- Introduction to hierarchical matrices with applications.
- LAPACK Users' Guide
- Matrix multiplication via arithmetic progressions
- Methods of conjugate gradients for solving linear systems
- Nested Dissection of a Regular Finite Element Mesh
- On the behaviour of upwind schemes in the low Mach number limit
- Optimizing the adaptive fast multipole method for fractal sets
- Rang revealing QR factorizations
- Solution of Linear Systems and Matrix Inversion in the TT-Format
- Solution of Sparse Indefinite Systems of Linear Equations
- The application of preconditioning in viscous flows
- The black-box fast multipole method
- The fast multipole method: Numerical implementation
- The inverse fast multipole method: using a fast approximate direct dolver as a preconditioner for dense linear systems
- Triangular Factorization and Inversion by Fast Matrix Multiplication
Cited in
(29)- A hierarchical algorithm for making sparse matrices sparser
- An extended compact profile iterative method criterion for sparse \(H\)-matrices
- Hierarchical orthogonal factorization: sparse least squares problems
- A robust hierarchical solver for ill-conditioned systems with applications to ice sheet modeling
- Efficient preconditioning of \(h p\)-FEM matrix sequences with slowly-varying coefficients: an application to topology optimization
- Distributed-memory hierarchical interpolative factorization
- An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation
- Parallelization of the inverse fast multipole method with an application to boundary element method
- A fast, memory efficient and robust sparse preconditioner based on a multifrontal approach with applications to finite-element matrices
- Matrices with hierarchical low-rank structures
- ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices
- Low-Rank Factorizations in Data Sparse Hierarchical Algorithms for Preconditioning Symmetric Positive Definite Matrices
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- A Hierarchical Preconditioner for Wave Problems in Quasilinear Complexity
- Hierarchical orthogonal factorization: sparse square matrices
- An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
- Sparse Hierarchical Preconditioners Using Piecewise Smooth Approximations of Eigenvectors
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems
- Randomized sparse direct solvers
- On the complexity of the block low-rank multifrontal factorization
- Bridging the gap between flat and hierarchical low-rank matrix formats: the multilevel block low-rank format
- The inverse fast multipole method: using a fast approximate direct dolver as a preconditioner for dense linear systems
- An Incomplete Cholesky Preconditioner Based on Orthogonal Approximations
- Hierarchical subspace evolution method for super large parallel computing: A linear solver and an eigensolver as examples
- Second‐order accurate hierarchical approximate factorizations for solving sparse linear systems
- Sparse hierarchical solvers with guaranteed convergence
- Parallel accelerated cyclic reduction preconditioner for three-dimensional elliptic PDEs with variable coefficients
- Quasi-optimal hierarchically semi-separable matrix approximation
This page was built for publication: Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5738178)
