GENERALIZED BLOCK-TRIDIAGONAL MATRIX ORDERINGS FOR PARALLEL COMPUTATION IN-PROCESS FLOWSHEETING

A new graph partitioning algorithm for use on structurally unsymmetric systems is presented. Unlike other partitioning algorithms that have been used to provide reorderings for structurally symmetric matrices, this algorithm employs a bipartite graph model, and hence, can be used to consider unsymmetric permutations of structurally unsymmetric matr ices. It is shown that the algorithm can be used in identifying coarse -granular, balanced tasks in the direct solution of flowsheeting matri ces by parallel techniques based on generalized block-tridiagonal and nested-block-tridiagonal matrix structures. It is also shown that such reorderings can be obtained inexpensively, in worst-case running time s that increase linearly with the order of the matrix.