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

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) for proper convergence. The choice of an effective preconditioner is highly problem dependent. We propose a novel fully algebraic sparse matrix solve algorithm. The computational complexity is linear under the assumption that fill-in blocks have bounded rank. 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, 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.

Publication year:2017

BOF-keylabel:yes

IOF-keylabel:yes

BOF-publication weight:2

CSS-citation score:2

Authors:International

Authors from:Higher Education