Multilevel Mesh Partitioning for Optimising Domain Shape

C. Walshaw, M. Cross, R. Diekmann and F. Schlimbach


Multilevel algorithms are a successful class of optimisation techniques which address the mesh partitioning problem. They usually combine a graph contraction algorithm together with a local optimisation method which refines the partition at each graph level. To date these algorithms have been used almost exclusively to minimise the cut-edge weight in the graph with the aim of minimising the parallel communication overhead. However it has been shown that for certain classes of solution algorithm, the convergence of the solver is strongly influenced shape or aspect ratio of the subdomains. In this paper therefore, we modify the multilevel algorithms in order to optimise a cost function based on aspect ratio. Several variants of the algorithms are tested and shown to provide excellent results.

Keywords: graph-partitioning, mesh-partitioning, multilevel algorithms, aspect ratio, domain decomposition preconditioning.

Fri Aug 13 13:41:14 BST 2004