Summary
The Rank Structured Cholesky (RSC) solver was developed by Jeff Chadwick (Ph.D. 2013) in joint work with me; it is based on Tim Davis’s CHOLMOD, a widely-used standard sparse Cholesky solver. Unlike CHOLMOD, the RSC solver takes advantage of low-rank block structure that appears naturally in many large linear systems that arise in elliptic PDE discretizations, and so has good scaling properties in both time and memory complexity. Unlike some other solvers based on similar ideas, the RSC solver also has good performance in practice, as it is engineered from the ground up to make good use of fast level-3 BLAS routines.
Papers
@techreport{2015-rsc,
author = {Chadwick, Jeffrey and Bindel, David},
title = {An Efficient Solver for Sparse Linear Systems Based on
Rank-Structured {Cholesky} Factorization},
month = jul,
year = {2015},
arxiv = {1507.05593},
link = {http://arxiv.org/pdf/1507.05593},
code = {https://github.com/jeffchadwick/rank_structured_cholesky},
status = {unrefereed}
}
Abstract:
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 Ax=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.
Talks
An Efficient Solver for Sparse Linear Systems based on Rank-Structured Cholesky Factorization
TSIMF Workshop on Structured Matrix Computations with Applications
rsc
•
meeting external invited
An Efficient Solver for Sparse Linear Systems based on Rank-Structured Cholesky Factorization
SIAM LA 2015
rsc
•
minisymposium external invited
An Efficient Solver for Sparse Linear Systems based on Rank-Structured Cholesky Factorization
Workshop on Forty Years of Nested Dissection, University of Waterloo
rsc
•
meeting external