2021 journal article
RCHOL: Randomized Cholesky factorization for solving SDD linear systems
SIAM Journal on Scientific Computing, 43(6), C411–C438.
TL;DR:
A randomized algorithm, namely {\tt rchol], is introduced to construct an approximate Cholesky factorization for a given sparse Laplacian matrix and is proved to be breakdown free and applied to solving linear systems with symmetric diagonally-dominant matrices.
(via Semantic Scholar)
open access via arxiv.org (repository)
Source: ORCID
Added: November 1, 2023
We introduce a randomized algorithm, namely {\tt rchol}, to construct an approximate Cholesky factorization for a given sparse Laplacian matrix (a.k.a., graph Laplacian). The (exact) Cholesky factorization for the matrix introduces a clique in the associated graph after eliminating every row/column. By randomization, {\tt rchol} samples a subset of the edges in the clique. We prove {\tt rchol} is breakdown free and apply it to solving linear systems with symmetric diagonally-dominant matrices. In addition, we parallelize {\tt rchol} based on the nested dissection ordering for shared-memory machines. Numerical experiments demonstrated the robustness and the scalability of {\tt rchol}. For example, our parallel code scaled up to 64 threads on a single node for solving the 3D Poisson equation, discretized with the 7-point stencil on a $1024\times 1024 \times 1024$ grid, or \textbf{one billion} unknowns.