On constructing the elimination tree

AbstractWe present a new algorithm for constructing the elimination tree for the Cholesky factor of an irreducible, symmetric, positive definite matrix A. The new algorithm runs in time O(m + nα(n, n)); the previous best asymptotic algorithm runs in time O(mα(m, n)), where m is the number of nonzero elements in the n × n matrix A and α(m, n) is a functional inverse of Ackermann's function (and grows very slowly). Thus the new algorithm is a small asymptotic improvement over the previous best algorithm if the density of the matrix is greater than O(n), and is the asymptotic equivalent of the previous algorithm otherwise. The new algorithm has an unusual form: reduce the graph corresponding to matrix A into a minimum spanning tree (MST) by an appropriate weight assignment, then construct the elimination tree by applying the existing algorithm to the MST obtained