next up previous

8.4 Parallelism in Sparse Factorization     continued...

Finally, Figure 9 shows the same problem reordered by odd--even reduction. This is not a general purpose strategy for sparse matrices, but it is often used to enhance parallelism in tridiagonal and related systems, so we illustrate it for the sake of comparison with more general purpose methods. In odd--even reduction (see, e.g., [55]), odd node numbers come before even node numbers, and then this same renumbering is applied recursively within each resulting subset, and so on until all nodes are numbered. Although the resulting nonzero pattern of A looks superficially different, we can see from the elimination tree that this method is essentially equivalent to nested dissection for this type of problem.

Figure 9: Graph and matrix reordered by odd--even reduction (left), with corresponding Cholesky factor and elimination tree (right).