SOURCE-LINKED INTELLIGENCE

CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs

arXiv · AI, language, vision and robotics · article · Sep 8, 2026 · UTC

Graph-data workloads such as diffusion estimation, ranking, semi-supervised learning, and network optimization often solve many Laplacian or symmetric diagonally dominant M-matrix (SDDM) systems with the same coefficient matrix. Approximate Cholesky preconditioners eliminate vertices one at a time and store the resulting sparse approximate factorization, the \emph{factor}, whose construction cost is amortized across these solves. But eliminating a vertex, the \emph{pivot}, creates a dense Schur-complement clique among its $d$ active neighbors. We introduce CAST (Canonical Approximate Schur Tre

Read original source ↗ Open in workspace

recordType

paper

region

Global