next up previous

8.4 Parallelism in Sparse Factorization     continued...

At any stage of the minimum degree algorithm, there may be more than one node with the same minimum degree, and the quality of the ordering produced may be affected by the tie breaking strategy used. In the example of Figure 7, we have deliberately broken ties in the most favorable way (with respect to parallelism); the least favorable tie breaking would have reproduced the original ordering of Figure 6, resulting in no parallelism. Breaking ties randomly (which in general is about all one can do) could produce anything in between these two extremes, yielding an elimination tree that reveals some large-grain parallelism, but which is taller and less well balanced than our example in Figure 7. Again, this is typical of minimum degree orderings. In view of this property, Liu [64] has developed an interesting strategy for further reordering of an initial minimum degree ordering that preserves fill while reducing the height of the elimination tree.

Figure 8 shows the same mesh again, this time ordered by nested dissection, a divide-and-conquer strategy [66]. Let S be a set of nodes, called a separator, whose removal, along with all edges incident upon nodes in S, disconnects into two remaining subgraphs. The nodes in each of the two remaining subgraphs are numbered contiguously and the nodes in the separator S are numbered last. This procedure is then applied recursively to split each of the remaining subgraphs, and so on, until all nodes have been numbered. If sufficiently small separators can be found, then nested dissection tends to do a good job of limiting fill, and if the pieces into which the graph is split are of about the same size, then the elimination tree tends to be well balanced. We see in Figure 8 that for our example, with this ordering, the Cholesky factor L suffers fill in two matrix entries (indicated by +), but the elimination tree now shows a fourfold large-grain parallelism, and its height has been reduced further. This behavior is again typical of nested dissection orderings: they tend to be somewhat less successful at limiting fill than minimum degree, but their divide-and-conquer nature tends to identify parallelism more systematically and produce better balanced elimination trees.

Figure 8: Graph and matrix reordered by nested dissection (left), with corresponding Cholesky factor and elimination tree (right).