RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems

Chao Chen, Tianyu Liang, George Biros

We introduce a randomized algorithm, namely RCHOL, to construct an approximate Cholesky factorization for a given Laplacian matrix (a.k.a., graph Laplacian). From a graph perspecti…