Elimination Structures in Scientific Computing:The Clique Tree

The Clique Tree

Chordal Graphs and Clique Trees

The filled graph G+(A) that results from the elimination game on the matrix A (the adjacency graph of the Cholesky factor L) is a chordal graph, i.e., a graph in which every cycle on four or more vertices has an edge joining two non-consecutive vertices on the cycle [63].

(The latter edge is called a chord, whence the name chordal graph. This class of graphs has also been called triangulated or rigid circuit graphs.)

A vertex v in a graph G is simplicial if its neighbors adj(v) form a clique. Every chordal graph is either a clique, or it has two non-adjacent simplicial vertices. (The simplicial vertices in the filled graph in Fig. 59.1 are 1, 2, 3, 4, 7, 8, and 9.) We can eliminate a simplicial vertex v without causing any fill by the rules of the elimination game, since adj(v) is already a clique, and no fill edge needs to be added. A chordal graph from which a simplicial vertex is eliminated continues to be a chordal graph. A perfect elimination ordering of a chordal graph is an ordering in which simplicial vertices are eliminated successively without causing any fill during the elimination game. A graph is chordal if and only if it has a perfect elimination ordering.

Suppose that the vertices of the adjacency graph G(A) of a sparse, symmetric matrix A have been re-numbered in an elimination ordering, and that G+(A) corresponds to the filled graph obtained by the elimination game on G(A) with that ordering. This elimination ordering is a perfect elimination ordering of the filled graph G+ (A). Many other perfect elimination orderings are possible for G+(A), since there are at least two simplicial vertices that can be chosen for elimination at each step, until the graph has one uneliminated vertex.

It is possible to design efficient algorithms on chordal graphs whose time complexity is much less than O(|E ∪ F |), where E ∪ F denotes the set of edges in the chordal filled graph.

This is accomplished by representing chordal graphs by tree data structures defined on the maximal cliques of the graph. (Recall that a clique K is maximal if K ∪ {v} is not a clique for any vertex v j∈ K.)

In practice, a rooted clique tree is used in sparse matrix computations. Lewis, Peyton, and Pothen [48] and Pothen and Sun [62] have designed algorithms for computing rooted clique trees. The former algorithm uses the adjacency lists of the filled graph as input, while the latter uses the elimination tree. Both algorithms identify representative vertices by a simple degree test. We will discuss the latter algorithm.

First, to define the concepts needed for the algorithm, consider that the the maximal cliques are ordered according to their representative vertices. This ordering partitions each maximal clique K(v) with representative vertex v into two subsets: new(K(v)) consists of vertices in the clique K(v) whose higher adjacency sets are contained in it but not in any earlier ordered maximal clique. The residual vertices in K(v) \ new(K(v)) form the ancestor set anc(K(v)). If a vertex w ∈ anc(K(v)), by definition of the ancestor set, w has a higher neighbor that is not adjacent to v; then by the rules of the elimination game, any higher-

FIGURE 59.6: An algorithm for computing a clique tree from an elimination tree, whose vertices are numbered in postorder. The variable hd+(v) is the higher degree of a vertex v in the filled graph.

numbered vertex x ∈ K(v) also belongs to anc(K(v)). Thus the partition of a maximal clique into new and ancestor sets is an ordered partition: vertices in new(K(v)) are ordered before vertices in anc(K(v)). We denote the lowest numbered vertex f in anc(K(v)) the first ancestor of the clique K(v). A rooted clique tree may be defined as follows: the parent of a clique K(v) is the clique P in which the first ancestor vertex f of K appears as a vertex in new(P ).

The reason for calling these subsets ‘new’ and ‘ancestor’ sets can be explained with respect to a rooted clique tree. We can build the chordal graph beginning with the root clique of the clique tree, successively adding one maximal clique at a time, proceeding down the clique tree in in-order. When a maximal clique K(v) is added, vertices in anc(K(v)) also belong to some ancestor clique(s) of K(v), while vertices in new(K(v)) appear for the first time. A rooted clique tree, with vertices in new(K) and anc(K) identified for each clique K, is shown in Fig. 59.7.

This clique tree algorithm can be implemented in O(n) time, once the elimination tree and the higher degrees have been computed. The rooted clique tree shown in Fig. 59.7, is computed from the example elimination tree and higher degrees of the vertices in the example filled graph, using the clique tree algorithm described above. The clique tree obtained from this algorithm is not unique. A second clique tree that could be obtained has the clique K(5) as the root clique, and the other cliques as leaves.

A comprehensive review of clique trees and chordal graphs in sparse matrix computations, current as of 1991, is provided by Blair and Peyton [7].

Design of Efficient Algorithms with Clique Trees

Shortest Elimination Trees. Jess and Kees [46] introduced the problem of modifying a fill-reducing elimination ordering to enhance concurrency in a parallel factorization algo- rithm. Their approach was to generate a chordal filled graph from the elimination ordering, and then to eliminate a maximum independent set of simplicial vertices at each step, until all the vertices are eliminated. (This is a greedy algorithm in which the largest number of pairwise independent columns that do not cause fill are eliminated in one step.) Liu

FIGURE 59.7: A clique tree of the example filled graph, computed from its elimination tree. Within each clique K in the clique tree, the vertices in new(K) are listed below the bar, and the vertices in anc(K) are listed above the bar.

and Mirzaian [55] showed that this approach computed a shortest elimination tree over all perfect elimination orderings for a chordal graph, and provided an implementation linear in the number of edges of the filled graph. Lewis, Peyton, and Pothen [55] used the clique tree to provide a faster algorithm; their algorithm runs in time proportional to the size of the clique tree: the sum of the sizes of the maximal cliques of the chordal graph.

A vertex is simplicial if and only if it belongs to exactly one maximal clique in the chordal graph; a maximum independent set of simplicial vertices is obtained by choosing one such vertex from each maximal clique that contains simplicial vertices, and thus the clique tree is a natural data structure for this problem. The challenging aspect of the algorithm is to update the rooted clique tree when simplicial vertices are eliminated and cliques that become non-maximal are absorbed by other maximal cliques.

Parallel Triangular Solution. In solving systems of linear equations by factorization methods, usually the work involved in the factorization step dominates the work involved in the triangular solution step (although the communication costs and synchronization overheads of both steps are comparable). However, in some situations, many linear systems with the same coefficient matrix but with different right-hand-side vectors need to be solved. In such situations, it is tempting to replace the triangular solution step involving the factor matrix L by explicitly computing an inverse L−1 of the factor. Unfortunately L−1 can be much less sparse than the factor, and so a more space efficient ‘product-form inverse’ needs to be employed. In this latter form, the inverse is represented as a product of triangular matrices such that all the matrices in the product together require exactly as much space as the original factor.

The computation of the product form inverse leads to some interesting chordal graph partitioning problems that can be solved efficiently by using a clique tree data structure.

We begin by directing each edge in the chordal filled graph G+(A) from its lower to its higher numbered end point to obtain a directed acyclic graph (DAG). We will denote this DAG by G(L). Given an edge (i, j) directed from i to j, we will call i the predecessor of j, and j the successor of i. The elimination ordering must eliminate vertices in a topological ordering of the DAG such that all predecessors of a vertex must be eliminated before it can be eliminated. The requirement that each matrix in the product form of the inverse must have the same nonzero structure as the corresponding columns in the factor is expressed by the fact that the subgraph corresponding to the matrix should be transitively closed. (A directed graph is transitively closed if whenever there is a directed path from a vertex i to a vertex j, there is an edge directed from i to j in the graph.) Given a set of vertices Pi, the column subgraph of Pi includes all the vertices in Pi and vertices reached by directed edges leaving vertices in Pi; the edges in this subgraph include all edges with one or both endpoints in Pi.

The simpler of the graph partitioning problems is the following:

Find an ordered partition P1 ≺ P2 ≺ ... Pm of the vertices of a directed acyclic filled graph G(L) such that 1. every v ∈ Pi has all of its predecessors included in P1, .. ., Pi; 2. the column subgraph of Pi is transitively closed; and

3. the number of subgraphs m is minimum over all topological orderings of G(L).

Pothen and Alvarado [61] designed a greedy algorithm that runs in O(n) time to solve this partitioning problem by using the elimination tree.

A more challenging variant of the problem minimizes the number of transitively closed subgraphs in G(L) over all perfect elimination orderings of the undirected chordal filled graph G+ (A). This variant could change the edges in the DAG G(L), (but not the edges in G+(A)) since the initial ordering of the vertices is changed by the perfect elimination ordering, and after the reordering, edges are directed from the lower numbered end point to its higher numbered end point.

This is quite a difficult problem, but two surprisingly simple greedy algorithms solve it. Peyton, Pothen, and Yuan provide two different algorithms for this problem; the first algorithm uses the elimination tree and runs in time linear in the number of edges in the filled graph [59]. The second makes use of the clique tree, and computes the partition in time linear in the size of the clique tree [60]. Proving the correctness of these algorithms requires a careful study of the properties of the minimal vertex separators (these are vertices in the intersections of the maximal cliques) in the chordal filled graph.

Compact Clique Trees

In analogy with skeleton graphs, we can define a space-efficient version of a clique tree representation of a chordal graph, called the compact clique tree. If K is the parent clique of a clique C in a clique tree, then it can be shown that anc(C) ⊂ K. Thus trading space for computation, we can delete the vertices in K that belong to the ancestor sets of its children, since we can recompute them when necessary by unioning the ancestor sets of the children. The partition into new and ancestor sets can be obtained by storing the lowest numbered ancestor vertex for each clique. A compact clique Kc corresponding to a clique K is:

Note that the compact clique depends on the specific clique tree from which it is computed. A compact clique tree is obtained from a clique tree by replacing cliques by compact cliques for vertices. In the example clique tree, the compact cliques of the leaves are un- changed from the corresponding cliques; and the compact cliques of the interior cliques are Kc(5) = {11}, and Kc(7) = {7, 8, 9}.

The compact clique tree is potentially sparser (asymptotically O(n) instead of O(n2) even) than the skeleton graph on pathological examples, but on “practical” examples, the size difference between them is small. Compact clique trees were introduced by Pothen and Sun [62].