RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems
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