Mesh partitioning: A multilevel balancing and refinement algorithm

Multilevel algorithms are a successful class of optimization techniques whi ch addresses the mesh partitioning problem. They usually combine a graph co ntraction algorithm together with a local optimization method which refines the partition at each graph level. In this paper we present an enhancement of the technique which uses imbalance to achieve higher quality partitions . We also present a formulation of the Kernighan-Lin partition optimization algorithm which incorporates load-balancing. The resulting algorithm is te sted against a different but related state-of-the-art partitioner and shown to provide improved results.