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.