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.