CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs

DOI10.48550/arXiv.2609.09255MaRDI QIDQ7288238arXivFDO

Authors Meher Chaitanya, Cameron Musco, Aristides Gionis

Publication date 8 September 2026

Published in arXiv

Tldr This paper introduces CAST (Canonical Approximate Schur Tree), a novel method for constructing approximate Cholesky preconditioners by replacing dense Schur-complement cliques with weighted random spanning trees sampled directly from them. CAST has an unbiased and connected update, minimizes the largest normalized reweighted-edge contribution among unbiased inverse-marginal one-tree estimators, and can be used to construct CAST-$ρ$, a variant that reduces certified local sampling variability at increased construction cost and downstream fill.

Full work available at URL https://doi.org/10.48550/arXiv.2609.09255

arXiv classification

cs.LGmath.NAstat.ML

Cites work

• A matrix Chernoff bound for strongly Rayleigh distributions and spectral sparsifiers from a few random spanning trees
• A Nearly-m log n Time Solver for SDD Linear Systems
• Approximate Gaussian elimination for Laplacians -- fast, sparse, and simple
• Determinantal probability measures
• Graph Sparsification by Effective Resistances
• Introduction to Graph Theory
• iSIRA: integrated shift-invert residual Arnoldi method for graph Laplacian matrices from big data
• Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver
• Local graph partitioning using PageRank vectors
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• PageRank beyond the web
• RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems
• Sampling random spanning trees faster than matrix multiplication
• Solving SDD linear systems in nearly \(m \log^{1/2} n\) time
• Sparsified Cholesky and multigrid solvers for connection Laplacians
• Ultrasparse ultrasparsifiers and faster Laplacian system solvers

This page was built for publication: CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7288238)