Deriving the Sparse Cholesky Elimination Tree for Matrix Factorization

Summary

This article provides a technical derivation of the elimination tree for the right-looking sparse Cholesky algorithm (A = LL^T) for sparse matrices. The author explains how this tree serves as the foundation for most sparse factorization software, revealing two key insights: where fill-in nonzeros appear in matrix L that weren't in the original A, and the task dependency graph for the factorization process. Unlike traditional presentations that build from sparse triangular solves, the author derives the elimination tree directly from the Cholesky factorization itself.