Fast hierarchical solvers for sparse matrices

Sparse linear systems are ubiquitous in various scientific computing applications. Inversion of sparse matrices with standard direct solve schemes are prohibitive for large systems due to their quadratic/cubic complexity. Iterative solvers, on the other hand, demonstrate better scalability. However, they suffer from poor convergence rates when used without a preconditioner. There are many preconditioners developed for different problems, such as ILU, AMG, Gauss-Seidel, etc. 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.