VAC: A Volume-sampling-based Elimination Rule for Approximate Cholesky Factorization

We propose Volume Appproximate Cholesky (VAC), an alternative sampling rule for practical approximate Cholesky algorithms. Our rule samples a uniformly random spanning tree of the arising product clique to reduce the fill-in generated at each step. Sampling a random spanning tree preserves the edgewise marginals of the provably correct scheme of (Kyng & Sachdeva 2016), while ensuring connectivity in the spirit of the practical rule proposed in (Gao, Kyng & Spielman 2023). Our sampling method is simple, provably linear time and also admits a O(log n) depth parallel implementation.