1\chapter{{\tt ETree}: Elimination and Front Trees}
2\label{chapter:ETree}
3\par
4The {\tt ETree} object is used to model an elimination tree or a
5front tree for a sparse factorization with symmetric structure.
6The tree is defined over a set of vertices in a graph --- the graph
7can be unit weight or non-unit weight.
8A ``node'' in the tree can be a single vertex (in the context of
9an elimination tree) or a group of vertices (as for a front tree).
10\par
11The tree information is stored as a {\tt Tree} object.
12In addition there are three {\tt IV} objects.
13One stores the total size of the nodes in the fronts,
14one stores the size of the boundaries of the fronts,
15and one stores the map from the vertices to the fronts.
16\par
17There is a great deal of functionality embodied into the {\tt ETree}
18object.
19Given an elimination tree or a front tree, one can extract the
20permutation vectors (for the fronts or the vertices), extract a
21multisector based on several criteria, compress the front tree in
22several ways, justify the tree (order children of a node in
23meaningful ways), evaluate metric vectors on the tree (heights,
24depths, subtree accumulators).
25\par
26The front tree we obtain from a low-fill matrix ordering is usually
27not the front tree that drives the factorization.
28We provide three methods that transform the former into the latter.
29One method merges the fronts together in a
30way that adds logical zeros to their structure.
31One method splits large fronts into smaller fronts.
32One method combines these two functionalities.
33
34