Partitioning a chordal graph into transitive subgraphs for parallel sparse triangular solution

A recent approach for solving sparse triangular systems of equations on massively parallel computers employs a factorization of the triangular coefficient matrix to obtain a representation of its inverse in product 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 the complexity of the parallel algorithm can be minimized. Algorithms for minimizing the number of factors over several classes of permutations have been considered in earlier work. Let $F=L+L^T$ denote the symmetric filled matrix corresponding to a Cholesky factor $L$, and let $G_F$ denote the adjacency graph of $F$. In this paper we consider the problem of minimizing the number of factors over all permutations which preserve the structure of $G_F$. The graph model of this problem is to partition the vertices $G_F$ into the fewest transitively closed subgraphs over all perfect elimination orderings while satisfying a certain precedence relationship. 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 current elimination graph. This solution relies on several results concerning {\em transitive perfect elimination orderings\/} introduced in this paper. We describe a partitioning algorithm with $\order{|V|+|E|}$ time and space complexity.