A parallel graph partitioning algorithm for a message-passing multiprocessor

We develop a parallel algorithm for partitioning the vertices of a graph into $p \geq 2$ sets in such a way that few edges connect vertices in different sets. The algorithm is intended for a message-passing multiprocessor system, such as the hypercube, and is based on the Kernighan-Lin algorithm for finding small edge separators on a single processor. We use this parallel partitioning algorithm to find orderings for factoring large sparse symettric positive definite matrices. These orderings not only reduce fill, but also result in good processor utilization and low communication overhead during the factorization. We provide a complexity analysis of the algorithm, as well as some numerical results from an Intel hypercube and a hypercube simulator.