# A Parallelisable 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.
It is designed to work efficiently in parallel as well as sequentially and
can be applied directly to dynamically refined meshes.
In addition,
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.

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

* *

Fri Aug 13 13:40:40 BST 2004