  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.
