A Data Structure for Parallel L/U Decomposition

Publisher Website
Google Scholar
Abstract
Some new results are presented concerning the pivoting of large systems of linear equations with respect to parallel processing techniques. It will be assumed that the processing of a pivot takes one time slot. The pivoting problem is studied by means of an associated graph model. Given a triangulated graph a set of label classes is established. Class k contains all pivots which may be processed in parallel during the kth time slot. The label classes are used to establish the elimination-tree (e-tree). The e-tree is a spanning tree for the given graph. The critical path in the e-tree indicates the minimum number of time slots necessary to complete the L/U-decomposition. Furthermore, the earliest and latest admissible time slot for the processing of every pivot may be derived, such that the critical path is not affected. The e-tree can be seen as a data structure to guide parallel processing based on sparsity.