Derives the column elimination tree directly from right-looking sparse Cholesky, revealing fill-in pattern and task dependency graph via an O(n) structure.
Key Takeaways
The elimination tree encodes two things: where fill-in nonzeros appear in L, and the task dependency DAG for the factorization.
Starting from dense right-looking Cholesky, redundant edges in the column DAG collapse into a tree via the structural rule: k < j <= i, L[i][k]!=0 and L[j][k]!=0 implies L[i][j]!=0.
compute_elimination_tree runs in O(n) using an ancestor path-compression walk over lower-triangular row patterns of A.
Symbolic factorization (symbolic_cholesky) uses the parent array plus original nonzero pattern to precompute all L column indices before numeric work begins.
This tree underlies most sparse factorization software even when A is not symmetric positive definite.
