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

A linear time algorithm is presented solving the following problem: Given a chordal graph \(G=(V,E)\), find a perfect elimination ordering \((v_ 1,v_ 2, \dots,v_ n)\) of \(G\) and a partition \((R_ 1,R_ 2,\dots,R_ t)\) of \(V\) such that \(t\) is minimum with respect to following conditions: \(v_ p \in R_ i\) and \(v_ q \in R_ j\) implies \(i \leq j\) for all indices \(p\) and \(q\) with \(1 \leq p<q \leq n\), and \(\{v_ p,v_ q\}\), \(\{v_ q,v_ r\} \in E\) implies \(\{ v_ p,v_ r\} \in E\) for all \(p\), \(q\), \(r\) and \(i\) with \(v_ p,v_ q,v_ r \in R_ i\) and \(1 \leq p<q<r \leq n\). This problem is related to an approach for solving sparse triangular systems of equations on parallel computers. This approach employs a factorization of the triangular coefficient matrix \(L\) to obtain a representation of its inverse in product form, where the number of required communication steps is proportional to the number of factors in the factorization. Let \(F=L+L^ T\) denote the symmetric filled matrix corresponding to a Cholesky factor \(L\). Then the adjacency graph \(G\) of \(F\) is chordal. Minimizing the number of factors over all permutations preserving the nonzero structure of \(F\) is equivalent to the above problem on \(G\).