Elimination Structures in Scientific Computing:Clique Covers and Quotient Graphs

Clique Covers and Quotient Graphs

Clique covers and quotient graphs are data structures that were developed for the efficient implementation of minimum-degree reordering heuristics for sparse matrices. In Gaussian elimination, an elimination step that uses aij as a pivot (the elimination of the jth un-known using the ith equation) modifies every coefficient akl for which akj j= 0 and ail j= 0.

Minimum-degree heuristics attempt to select pivots for which the number of modified coefficients is small.

Clique Covers

Recall the graph model of symmetric Gaussian elimination discussed in subsection 59.1.1. The adjacency graph of the matrix to be factored is an undirected graph G = (V, E), V = {1, 2,... , n}, E = {(i, j) : aij j= 0}. The elimination of a row/column j corresponds to eliminating vertex j and adding edges to the remaining graph so that the neighbors of j become a clique. If we represent the edge set E using a clique cover, a set of cliques K = {K : K ⊆ V } such that E = ∪K∈K{(i, j) : i, j ∈ K}, the vertex elimination process becomes a process of merging cliques [63]: The elimination of vertex j corresponds to merging all the cliques that j belongs to into one clique and removing j from all the cliques.

Clearly, all the old cliques that j used to belong to are now covered by the new clique, so they can be removed from the cover. The clique-cover can be initialized by representing every nonzero of A by a clique of size 2. This process corresponds exactly to symbolic elimination, which we have discussed in Section 59.2, and which costs Θ(|L|) work. The cliques correspond exactly to frontal matrices in the multifrontal factorization method.

In the sparse-matrix literature, this model of Gaussian elimination has been sometimes called the generalized-element model or the super-element model, due to its relationship to finite-element models and matrices.

The significance of clique covers is due to the fact that in minimum-degree ordering codes, there is no need to store the structure of the partially computed factor, so when one clique is merged into another, it can indeed be removed from the cover. This implies that the total size ),K∈K |K| of the representation of the clique cover, which starts at exactly |A|− n, shrinks in every elimination step, so it is always bounded by |A|− n. Since exactly one clique is formed in every elimination step, the total number of cliques is also bounded, by n + (|A|− n) = |A|. In contrast, the storage required to explicitly represent the symbolic factor, or even to just explicitly represent the edges in the reduced matrix, can grow in every elimination step and is not bounded by O(|A|).

Some minimum-degree codes represent cliques fully explicitly [8, 36]. This representation uses an array of cliques and an array of vertices; each clique is represented by a linked list of vertex indices, and each vertex is represented by a linked list of clique indices to which it belongs. The size of this data structure never grows—linked-list elements are moved from one list to another or are deleted during elimination steps, but new elements never need to be allocated once the data structure is initialized.

Most codes, however, use a different representation for clique covers, which we describe next.

Quotient Graphs

Most minimum-degree codes represent the graphs of reduced matrices during the elimination process using quotient graphs [25]. Given a graph G = (V, E) and a partition S of V into disjoint sets Sj ∈ S, the quotient graph G/S is the undirected graph (S, E) where E = {(Si, Sj ) : adj(Si) ∩ Sj j= ∅}.

The representation of a graph G after the elimination of vertices 1, 2,... ,j − 1, but before the elimination of vertex j, uses a quotient graph G/S, where S consists of sets Sk of eliminated vertices that form maximal connected components in G, and sets Si = {i} of uneliminated vertices i ≥ j. We denote a set Sk of eliminated vertices by the index k of the highest-numbered vertex in it.

This quotient graph representation of an elimination graph corresponds to a clique cover representation as follows. Each edge in the quotient graph between uneliminated vertices S{i1 } and S{i2 } corresponds to a clique of size 2; all the neighbors of an eliminated set Sk correspond to a clique, the clique that was created when vertex k was eliminated. Note that all the neighbors of an uneliminated set Sk are uneliminated vertices, since uneliminated sets are maximal with respect to connectivity in G.

The elimination of vertex j in the quotient-graph representation corresponds to marking Sj as eliminated and merging it with its eliminated neighbors, to maintain the maximal connectivity invariant.

Clearly, a representation of the initial graph G using adjacency lists is also a representation of the corresponding quotient graph. George and Liu [26] show how to maintain the quotient graph efficiently using this representation without allocating more storage through a series of elimination steps.

Most of the codes that implement minimum-degree ordering heuristics, such as GEN- MMD [50], AMD [2], and Spindle [14, 47], use quotient graphs to represent elimination graphs.

It appears that the only advantage of a quotient graph over an explicit clique cover in the context of minimum-degree algorithms is a reduction by a small constant factor in the storage requirement, and possibly in the amount of work required. Quotient graphs, however, can also represent symmetric partitions of symmetric matrices in applications that are not directly related to elimination graphs. For example, George and Liu use quotient graphs to represent partitions of symmetric matrices into block matrices that can be factored without fill in blocks that only contain zeros [29, Chapter 6].

In [27], George and Liu showed how to implement the minimum degree algorithm without modifying the representation of the input graph at all. In essence, this approach represents the quotient graph implicitly using the input graph and the indices of the eliminated vertices. The obvious drawback of this approach is that vertex elimination (as well as other required operations) are expensive.

The Problem of Degree Updates

The minimum-degree algorithm works by repeatedly eliminating the vertex with the minimum degree and turning its neighbors into a clique. If the reduced graph is represented by a clique cover or a quotient graph, then the representation does not reveal the degree of vertices. Therefore, when a vertex is eliminated from a graph represented by a clique cover or a quotient graph, the degrees of its neighbors must be recomputed. These degree updates can consume much of the running time of minimum-degree algorithms.

Practical minimum-degree codes use several techniques to address this issue. Some techniques reduce the running time while preserving the invariant that the vertex that is eliminated always has the minimum degree. For example, mass elimination, the elimination of all the vertices of a supernode consecutively without recomputing degrees, can reduce the running time significantly without violating this invariant. Other techniques, such as mul- tiple elimination and the use of approximate degrees, do not preserve the minimum-degree invariant. This does not imply that the elimination orderings that such technique produce are inferior to true minimum-degree orderings. They are often superior to them. This is not a contradiction since the minimum-degree rule is just a heuristic which is rarely optimal. For further details, we refer the reader to George and Liu’s survey [30], to Amestoy, Davis, and Duff’s paper on approximate minimum-degree rules [2], and to Kumfert and Pothen’s work on minimum-degree variants [14, 47]. Heggernes, Eisenstat, Kumfert and Pothen prove upper bounds on the running time of space-efficient minimum-degree variants [44].

Covering the Column-Intersection Graph and Biclique Covers Column orderings for minimizing fill in Gaussian elimination with partial pivoting and in the orthogonal-triangular (QR, where Q is an orthogonal matrix, and R is an upper triangular matrix) factorization are often based on symmetric fill minimization in the symmetric factor of AT A, whose graph is known as the the column intersection graph G (A) (we ignore the possibility of numerical cancellation in AT A). To run a minimum-degree algorithm on the column intersection graph, a clique cover or quotient graph of it must be constructed. One obvious solution is to explicitly compute the edge-set of G∩(A), but this is inefficient, since G∩(A) can be much denser than G(A).

A better solution is to initialize the clique cover using a clique for every row of A; the vertices of the clique are the indices of the nonzeros in that row [30]. It is easy to see that each row in A indeed corresponds to a clique in G∩(A). This approach is used in the COLMMD routine in Matlab [36] and in COLAMD [11].

A space-efficient quotient-graph representation for G∩(A) can be constructed by creating an adjacency-list representation of the symmetric 2-by-2 block matrix and eliminating vertices 1 through n. The graph of the Schur complement matrix G(0 − AT I(−1)A) = G(AT A) = G (A).

If we maintain a quotient-graph representation of the reduced graph through the first n elimination steps, we obtain a space-efficient quotient graph representation of the column- intersection graph. This is likely to be more expensive, however, than constructing the clique-cover representation from the rows of A. We learned of this idea from John Gilbert; we are not aware of any practical code that uses it.

The nonzero structure of the Cholesky factor of AT A is only an upper bound on the structure of the LU factors in Gaussian elimination with partial pivoting. If the identities of the pivots are known, the nonzero structure of the reduced matrices can be represented using biclique covers. The nonzero structure of A is represented by a bipartite graph ({1, 2,... , n}∪ {1t, 2t,..., nt}, {(i, jt) : aij j= 0}). A biclique is a complete bipartite graph on a subset of the vertices. Each elimination step corresponds to a removal of two connected vertices from the bipartite graph, and an addition of a new biclique. The vertices of the new biclique are the neighbors of the two eliminated vertices, but they are not the union of a set of bicliques. Hence, the storage requirement of this representation may exceed the storage required for the initial representation. Still, the storage requirement is always smaller than the storage required to represent each edge of the reduced matrix explicitly. This representation poses the same degree update problem that symmetric clique covers pose, and the same techniques can be used to address it. Version 4 of UMFPACK, an asymmetric multifrontal LU factorization code, uses this idea together with a degree approximation technique to select pivots corresponding to relatively sparse rows in the reduced matrix [9].