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
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
- 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
- A Direct Solver with $O(N)$ Complexity for Variable Coefficient Elliptic PDEs Discretized via a High-Order Composite Spectral Collocation Method
- 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
