PARTITIONING A CHORDAL GRAPH INTO TRANSITIVE SUBGRAPHS FOR PARALLEL SPARSE TRIANGULAR SOLUTION

A recent approach for solving sparse triangular systems of equations o n massively parallel computers employs a factorization of the triangul ar coefficient matrix to obtain a representation of its inverse in pro duct form. The number of general communication steps required by this approach is proportional to the number of factors in the factorization . The triangular matrix can be symmetrically permuted to minimize the number of factors over suitable classes of permutations, and thereby t he complexity of the parallel algorithm can be minimized. Algorithms f or minimizing the number of factors over several classes of permutatio ns have been considered in earlier work. Let F = L + L(T) denote the s ymmetric filled matrix corresponding to a Cholesky factor L, and let G (F) denote the adjacency graph of F. We consider the problem of minimi zing the number of factors over all permutations which preserve the st ructure of G(F). The graph model of this problem is to partition the v ertices G(F) into the fewest transitively closed subgraphs over all pe rfect elimination orderings while satisfying a certain precedence rela tionship. The solution to this chordal-graph partitioning problem can be described by a greedy scheme which eliminates a largest permissible subgraph at each step. Further, the subgraph eliminated at each step can be characterized in terms of lengths of chordless paths in the cur rent elimination graph. This solution relies on several results concer ning transitive perfect elimination orderings introduced in this paper . We describe a partitioning algorithm with O(Absolute value of V + Ab solute value of E) time and space complexity.