Ab. Coon et Ma. Stadtherr, GENERALIZED BLOCK-TRIDIAGONAL MATRIX ORDERINGS FOR PARALLEL COMPUTATION IN-PROCESS FLOWSHEETING, Computers & chemical engineering, 19(6-7), 1995, pp. 787-805
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.