An Efficient Solver for Sparse Linear Systems Based on Rank-Structured Cholesky Factorization
For scientists and engineers solving large sparse linear systems from PDEs, this method offers a more efficient direct solver that outperforms both traditional direct and iterative approaches.
The paper presents a sparse, rank-structured Cholesky solver for positive definite linear systems from PDE discretizations that reduces memory usage compared to standard sparse Cholesky and reduces wall-clock time compared to preconditioned iterative methods.
Direct factorization methods for the solution of large, sparse linear systems that arise from PDE discretizations are robust, but typically show poor time and memory scalability for large systems. In this paper, we describe an efficient sparse, rank-structured Cholesky algorithm for solution of the positive definite linear system $A x = b$ when $A$ comes from a discretized partial-differential equation. Our approach combines the efficient memory access patterns of conventional supernodal Cholesky algorithms with the memory efficiency of rank-structured direct solvers. For several test problems arising from PDE discretizations, our method takes less memory than standard sparse Cholesky solvers and less wall-clock time than standard preconditioned iterations.