Fast Hierarchical Solvers For Sparse Matrices Using Extended Sparsification and Low-Rank Approximation
From MaRDI portal
Publication:5738178
DOI10.1137/15M1046939zbMath1365.65072arXiv1510.07363MaRDI QIDQ5738178
Hadi Pouransari, Eric Darve, Pieter Coulier
Publication date: 31 May 2017
Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1510.07363
algorithmcomputational complexityGauss eliminationiterative methodsGMRESsparse matricespreconditionerLU factorizationhierarchical structureGauss-Seidel
Computational methods for sparse matrices (65F50) Direct numerical methods for linear systems and matrix inversion (65F05) Preconditioners for iterative methods (65F08)
Related Items (20)
Hierarchical orthogonal factorization: sparse least squares problems ⋮ ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices ⋮ Distributed-memory hierarchical interpolative factorization ⋮ An Incomplete Cholesky Preconditioner Based on Orthogonal Approximations ⋮ On the Complexity of the Block Low-Rank Multifrontal Factorization ⋮ 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 ⋮ An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations ⋮ Matrices with Hierarchical Low-Rank Structures ⋮ Parallelization of the inverse fast multipole method with an application to boundary element method ⋮ Bridging the Gap Between Flat and Hierarchical Low-Rank Matrix Formats: The Multilevel Block Low-Rank Format ⋮ A robust hierarchical solver for ill-conditioned systems with applications to ice sheet modeling ⋮ Sparse Hierarchical Preconditioners Using Piecewise Smooth Approximations of Eigenvectors ⋮ Sparse Approximate Multifrontal Factorization with Butterfly Compression for High-Frequency Wave Equations ⋮ The Inverse Fast Multipole Method: Using a Fast Approximate Direct Solver as a Preconditioner for Dense Linear Systems ⋮ Parallel accelerated cyclic reduction preconditioner for three-dimensional elliptic PDEs with variable coefficients ⋮ Efficient preconditioning of \(h p\)-FEM matrix sequences with slowly-varying coefficients: an application to topology optimization ⋮ 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
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
- Rang revealing QR factorizations
- A kernel-independent adaptive fast multipole algorithm in two and three dimensions
- An adaptive fast direct solver for boundary integral equations in two dimensions
- A direct solver with \(O(N)\) complexity for integral equations on one-dimensional domains
- Matrix multiplication via arithmetic progressions
- Hierarchical matrices. A means to efficiently solve elliptic boundary value problems
- The black-box fast multipole method
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- Adaptive low-rank approximation of collocation matrices
- Introduction to hierarchical matrices with applications.
- The application of preconditioning in viscous flows
- Algebraic multigrid theory: The symmetric case
- A sparse \({\mathcal H}\)-matrix arithmetic: General complexity estimates
- \(\mathcal H^2\)-matrix approximation of integral operators by interpolation
- On the behaviour of upwind schemes in the low Mach number limit
- The fast multipole method: Numerical implementation
- A fast block low-rank dense solver with applications to finite-element matrices
- 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
- Hierarchical Interpolative Factorization for Elliptic Operators: Integral Equations
- A Randomized Blocked Algorithm for Efficiently Computing Rank-revealing Factorizations of Matrices
- Divide and Conquer Low-Rank Preconditioners for Symmetric Matrices
- Fast algorithms for hierarchically semiseparable matrices
- Hierarchical Interpolative Factorization for Elliptic Operators: Differential Equations
- Condition Estimates
- Direct Methods for Sparse Linear Systems
- Fast direct solvers for integral equations in complex three-dimensional domains
- A FETI‐preconditioned conjugate gradient method for large‐scale stochastic finite element problems
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- LAPACK Users' Guide
- Generalized Nested Dissection
- A generalization of the fast LUP matrix decomposition algorithm and applications
- Computing the Minimum Fill-In is NP-Complete
- Solution of Sparse Indefinite Systems of Linear Equations
- Triangular Factorization and Inversion by Fast Matrix Multiplication
- A Block Algorithm for Matrix 1-Norm Estimation, with an Application to 1-Norm Pseudospectra
- ILUT: A dual threshold incomplete LU factorization
- Solution of Linear Systems and Matrix Inversion in the TT-Format
- Optimizing the Adaptive Fast Multipole Method for Fractal Sets
- A Fast $ULV$ Decomposition Solver for Hierarchically Semiseparable Representations
- A Fast Solver for HSS Representations via Sparse Matrices
- Nested Dissection of a Regular Finite Element Mesh
- The Inverse Fast Multipole Method: Using a Fast Approximate Direct Solver as a Preconditioner for Dense Linear Systems
- An algebraic multifrontal preconditioner that exploits the low‐rank property
- Methods of conjugate gradients for solving linear systems
- A fast algorithm for particle simulations
- A review of algebraic multigrid
This page was built for publication: Fast Hierarchical Solvers For Sparse Matrices Using Extended Sparsification and Low-Rank Approximation
