Matrix ordering strategies for process engineering: graph partitioning algorithms for parallel computation

The solution of large-scale chemical process simulation and optimization pr oblems using parallel computation requires algorithms that can take advanta ge of multiprocessing when solving the large, sparse matrices that arise. P arallel algorithms require that the matrices be partitioned in order to dis tribute computational work across processors. One way to accomplish this is to reorder the matrix into a bordered block-diagonal form. Since this stru cture is not always obtained from the equation generation routine, an algor ithm to reorder the rows and columns of the coefficient matrix is needed. W e describe here a simple graph partitioning algorithm that creates a border ed block-diagonal form that is suitable for use with parallel algorithms fo r the solution of the highly asymmetric sparse matrices arising in process engineering applications. The method aims to create a number of similarly s ized diagonal blocks while keeping the size of the interface matrix, which may represent a bottleneck in the parallel computation, reasonably small. R esults on a wide range of test problems indicate that the reordering algori thm is able to find such a structure in most cases, and requires much less reordering time than previously used graph partitioning methods. (C) 1999 E lsevier Science Ltd. All rights reserved.