An Algorithm for Computing an Elimination Tree of Minimum Height for a
Tree
Abstract
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.