next up previous

8.4 Parallelism in Sparse Factorization     continued...

Figure 7 shows the same one-dimensional mesh with the nodes reordered by a minimum degree algorithm. Minimum degree is the most effective general purpose heuristic known for limiting fill in sparse factorization [65]. In its simplest form, this algorithm begins by selecting a node of minimum degree (i.e. one having fewest incident edges) in and numbering it first. The selected node is then deleted and new edges are added, if necessary, to make its former neighbors into a clique. The process is then repeated on the updated graph, and so on, until all nodes have been numbered. We see in Figure 7 that L suffers no fill in the new ordering, and the elimination tree now shows some large-grain parallelism. In particular, columns 1 and 2 can be computed simultaneously, then columns 3 and 4, and so on. This twofold parallelism reduces the tree height (roughly the parallel completion time) by approximately a factor of two.

Figure 7: Graph and matrix reordered by minimum degree (left), with corresponding Cholesky factor and elimination tree (right).