A Localized Algorithm for Optimizing Unstructured Mesh Partitions

Abstract

A new method is described for optimizing graph parti tions that arise in mapping unstructured mesh calcula tions to parallel computers. The method employs a combination of iterative techniques to evenly balance the workload and minimize the number and volume of interprocessor communications. When combined with a fast direct-partitioning technique (such as the Greedy algorithm) to give an initial partition, the resulting two- stage process proves itself to be a powerful and flexi ble solution to the static graph-partitioning problem. A clustering technique can also be employed to speed up the whole process. Experiments, on graphs with up to a million nodes, indicate that the resulting code is up to an order of magnitude faster than existing state- of-the-art techniques such as Multilevel Recursive Spectral Bisection, while providing partitions of equiv alent quality.