An Algorithm for Computing an Elimination Tree of Minimum Height for a Tree


The elimination tree is a rooted tree that is computed from the adjacency graph of a symmetric matrix $A$. The height of the elimination tree is one restricting factor when solving a sparse linear system $Ax=b$ on a parallel computer using Cholesky factorization. An efficient algorithm is presented for the problem of ordering the nodes in a tree $G$ so that its elimination tree is of minimum height. Its running time is $O(n\log n\log d)$ where $n$ is the number of nodes in $G$ and $d$ the maximum degree of any node in $G$. The number of fill edges caused by this algorithm is less than $n$. We also show that there exists a minimal separator ordering on any matrix such that the resulting elimination tree is of minimum height. Implications of these results are given for the computation of elimination trees of minimum height for more general classes of graphs.