A LOCALIZED ALGORITHM FOR OPTIMIZING UNSTRUCTURED MESH PARTITIONS

A new method is described for optimizing graph partitions that arise i n mapping unstructured mesh calculations to parallel computers. The me thod employs a combination of iterative techniques to evenly balance t he workload and minimize the number and volume of interprocessor commu nications. When combined with a fast direct-partitioning technique (su ch as the Greedy algorithm) to give an initial partition, the resultin g two-stage process proves itself to be a powerful and flexible soluti on to the static graph-partitioning problem. A clustering technique ca n also be employed to speed up the whole process. Experiments, on grap hs 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 techniq ues such as Multilevel Recursive Spectral Bisection, while providing p artitions of equivalent quality.