Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation

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.

References in corpus (4)

• A Fast Block Low-Rank Dense Solver with Applications to Finite-Element Matrices
• The Inverse Fast Multipole Method
• Parallel variable-density particle-laden turbulence simulation
• Optimizing the adaptive fast multipole method for fractal sets

Cited by in corpus (11)

• Parallel Approximation of the Maximum Likelihood Estimation for the Prediction of Large-Scale Geostatistics Simulations
• Parallelization of the inverse fast multipole method with an application to boundary element method
• A Robust Hierarchical Solver for Ill-conditioned Systems with Applications to Ice Sheet Modeling
• Distributed-memory Hierarchical Interpolative Factorization
• Parallel accelerated cyclic reduction preconditioner for three-dimensional elliptic PDEs with variable coefficients
• Accelerated Cyclic Reduction: A Distributed-Memory Fast Solver for Structured Linear Systems
• Sparse Hierarchical Preconditioners Using Piecewise Smooth Approximations of Eigenvectors
• A hierarchical preconditioner for wave problems in quasilinear complexity
• Recursively Preconditioned Hierarchical Interpolative Factorization for Elliptic Partial Differential Equations
• Second Order Accurate Hierarchical Approximate Factorization of Sparse SPD Matrices
• Sparse Approximate Multifrontal Factorization with Butterfly Compression for High Frequency Wave Equations