Multilevel Mesh Partitioning for Optimising Aspect Ratio in Domain Decomposition Based Parallel Solvers

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, however it has been shown that for certain classes of solution algorithm, the convergence of the solver is strongly influenced by the subdomain aspect ratio. 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.

Fri Aug 13 13:41:10 BST 2004