We use the notation to denote the ith row, and to denote the jth column, of a matrix M. For a given sparse matrix M, we define
In other words, is the sparsity structure of row i of the strict lower triangle of M, while is the sparsity structure of column j of the strict lower triangle of M. For the Cholesky factor L, we define the parent function as follows:
Thus, is the row index of the first offdiagonal nonzero in column j of L, if any, and has the value j otherwise. Using the parent function, we define the elimination tree as a graph having n vertices, with an edge between vertices i and j, for i > j, if . If the matrix is irreducible, then the elimination tree is indeed a single tree with its root at vertex n (otherwise it is more accurately termed an elimination forest). The elimination tree, which we denote by , is a spanning tree for the filled graph . The many uses of the elimination tree in analyzing and organizing sparse Cholesky factorization are surveyed in . We will illustrate these concepts pictorially in several examples below.