rchol is a C++ library that implements a randomized incomplete Cholesky factorization. rchol is provably effective for SDDM matrices (Symmetric and Diagonally Dominant M-matrices), but can be tested on any SPD matrix. It uses OpenMP for shared memory parallelism on x86 architectures. We do not support GPUs.
Factorizing the discrete Laplacian matrix on a 1024x1024x1024 grid with standard 7-point stencil, which has one billion unknowns, takes about 3 minutes/180 seconds using 64 threads.
The underlying algorithm is based on Daniel Spielman's Julia implementation of a randomized incomplete factorization for graph Laplacians.
The corresponding paper that describes the details can be found here.
Dependencies: The only dependency is the METIS library. METIS is required for shared-memory parallelism.
ichol. We provide several examples for various matrices. In our experiments, rchol is 3X faster than the thresholded ichol for the same sparsity pattern (as of September 2020). At each directory, please check the README and makefile files.
Tianyu Liang
Chao Chen (chenchao.nk@gmail.com)
George Biros (advisor)
This project is partially funded by NSF award CCF-1817048; and by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program under Award Number DE-SC0019393, by the U.S. Department of Energy, National Nuclear Security Administration Award Number DE-NA000396 (PSAAP III). Computing time on the Texas Advanced Computing Centers Stampede system was provided by an allocation from TACC and the NSF.