Sparse Cholesky Elimination Tree

Source: Hacker News

—> April 09, 2026

Here I derive the elimination tree for the (right-looking) sparse Cholesky algorithm for computing A = LL^T for lower triangular L and sparse matrices A. This tree forms the foundation for most sparse factorization software, even when the underlying assumptions of Cholesky (symmetric and definite) do not apply. Ultimately this tree tells us two things: 1. where nonzeros appear in the matrix L even if not present in the original A (i.e. “fill-in”) and 2. the task dependency graph of our resulting factorization. Traditionally this concept is usually presented in the context sparse triangular solves which is then used as a building-block to a Cholesky factorization. I wanted to instead work directly from a Cholesky factorization, which is what I do below.

Motivating the Elimination Tree

Suppose at first we start with the plain dense right-looking Cholesky algorithm in pseudocode below:

// Input:  symmetric positive definite A, assigned to an output matrix L
// Output: lower triangular part of L is such that A = LL^T

for (int k = 0; k 1` and `0->2`. Since `0` has two “parents” this is a DAG pattern rather than a tree. But the above structural rule tells us that `0->2` is a redundant edge because `0->1` necessarily means `L[1,0]!=0`, and `0->2` necessarily means `L[2,0]!=0`, and thus we must have `L[2,1]!=0`, and so there is an implied edge `1->2`, and it is redundant information that `0->2` because we must proceed from `0->1` first anyways. If we remove all redundant edges from our column DAG, the result is a tree

![dagtree](https://www.reidatcheson.com/assets/etree/column_dag_vs_elimination_tree.svg)

The elimination tree tells us how to generate the fill-pattern of `L` from the initial nonzero pattern of `A` and the structural rule: `k = k for which L[i][k] exists
//
// Scratch:
//   mark[k] is overwritten.

void symbolic_cholesky(
    int n,
    int** A_row,
    int* A_row_len,
    int* parent,
    int* mark,
    vector_int* L_col
) {
    for (int k = 0; k k s.t. L[j,k]!=0}

To compute the elimination tree using only the starting nonzeros of A without excessive extra work we need to incrementally build parents. This means for each r we need to try and find the path to r in this tree.

So if we iterate through rows of A in order and then look at the column ids we get a candidate path c-> ... -> r. We save that c->r in ancestors[c] and iterate up ancestors until we found a column we have not yet matched, then that column’s parent becomes r, because we are iterating rows in order we can not find a smaller r.

In pseudo-C below:

// Compute the column elimination tree.
//
// Input:
//   n
//   A_row[r]      : columns c  ... -> r
            //
            // Walk upward from c through the paths already discovered.
            int v = c;

            while (v != -1 && v < r) {
                int next = ancestor[v];

                // Record that while processing row r, v has been
                // connected upward to r.
                ancestor[v] = r;

                if (next == -1) {
                    // This path stopped at v. Since rows are processed
                    // in increasing order, r is the first later row that
                    // needs v as an ancestor, so r is parent[v].
                    parent[v] = r;
                    break;
                }

                // Continue walking the previously discovered path.
                v = next;
            }
        }
    }
}

The presentation of elimination trees often involves some preliminary graph theory that always felt a little detatched from the linear algebra. My aim here was not to replace the graph theory, but to make it more grounded in the underlying algorithm. I proceeded directly from the right-looking Cholesky factorization to a task DAG, pruned that DAG, and then showed that the structural rule implied by step (3) of the algorithm results in a compressed representation of the task DAG, and that compressed representation happens to be a tree.