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

arXiv: https://arxiv.org/abs/2609.20241 · HTML: https://mlsanity.com/paper/2609.20241/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jul 2026.

## Built on by (most cited first, 1 of 1)

- [CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs](https://mlsanity.com/paper/2609.09255/) (2026)

## Abstract (arXiv)

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.