Multilevel mesh partitioning for optimizing domain shape

Multilevel algorithms are a successful class of optimization techniques tha t address the mesh partitioning problem for mapping meshes onto parallel co mputers. They usually combine a graph contraction algorithm together with a local optimization method that refines the partition at each graph level. To date, these algorithms have been used almost exclusively to minimize the cut-edge weight in the graph with the aim of minimizing the parallel commu nication overhead. However, it has been shown that for certain classes of p roblems, the convergence of the underlying solution algorithm is strongly i nfluenced by the shape or aspect ratio of the subdomains. Therefore, in thi s paper, the authors modify the multilevel algorithms to optimize a cost fu nction based on the aspect ratio. Several variants of the algorithms are te sted and shown to provide excellent results.