Metraipolis › archive › dc_2047f427b2de
VAC: A Volume-sampling-based Elimination Rule for Approximate Cholesky Factorization — arXiv:2609.20241
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.20241
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T05:39:45.819Z
- SHA-256 of the archived text
f4300daf825a55ba3ffc22e7ecbf4aa324dbe1b335417a92b3db798a8d5624ad- Stable URL of this page
https://metraipolis.com/documento/dc_2047f427b2de
How to cite
VAC: A Volume-sampling-based Elimination Rule for Approximate Cholesky Factorization — arXiv:2609.20241 — arXiv (en), https://arxiv.org/abs/2609.20241 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2047f427b2de (Metraipolis archive dc_2047f427b2de, sha256 f4300daf825a55ba3ffc22e7ecbf4aa324dbe1b335417a92b3db798a8d5624ad)
BibTeX
@misc{dc2047f427b2de,
title = {VAC: A Volume-sampling-based Elimination Rule for Approximate Cholesky Factorization — arXiv:2609.20241},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.20241},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2047f427b2de; sha256 f4300daf825a55ba3ffc22e7ecbf4aa324dbe1b335417a92b3db798a8d5624ad},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.20241. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-18 in cs.DS). Categorie arXiv: Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2609.20241 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-10T05:08:06.570Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).