next up previous

8.4 Parallelism in Sparse Factorization     continued...

Large-grain parallelism, at the level of subtrees of the elimination tree, is available only in the sparse case. If and are disjoint subtrees of the elimination tree, with neither root node a descendant of the other, then all of the columns corresponding to nodes in can be computed completely independently of the columns corresponding to nodes in , and vice versa, and hence these computations can be done simultaneously by separate processors with no communication between them. For example, each leaf node of the elimination tree corresponds to a column of L that depends on no prior columns, and hence all of the leaf node columns can be completed immediately merely by performing the corresponding operation on each of them. Furthermore, all such operations can be performed simultaneously by separate processors (assuming enough processors are available). By contrast, in the dense case all operations must be performed sequentially (at least at this level of granularity), since there is never more than one leaf node at any given time.