# A Localised Algorithm for Optimising Unstructured Mesh Partitions

**
****C. Walshaw, M. Cross and M. G. Everett**

### Abstract:

A new method is described for optimising graph partitions which
arise in mapping unstructured mesh calculations to parallel computers. The
method employs a combination of iterative
techniques to both evenly balance the workload and minimise
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 both a
powerful and flexible 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, whilst providing partitions
of equivalent quality.

**Key words.** graph-partitioning, unstructured meshes, load-balancing,
parallel scientific computation.

* *

Fri Aug 13 13:40:38 BST 2004