The Role of Elimination Trees in Sparse Factorization

In this paper, the role of elimination trees in the direct solution of large sparse linear systems is examined. The notion of elimination trees is described and its relation to sparse Cholesky factorization is discussed. The use of elimination trees in the various phases of direct factorization are surveyed: in reordering, sparse storage schemes, symbolic factorization, numeric factorization, and different computing environments.