Parallel optimisation algorithms for multilevel mesh partitioning

Three parallel optimisation algorithms, for use in the context of multileve l graph partitioning of unstructured meshes, are described. The first, inte rface optimisation, reduces the computation to a set of independent optimis ation problems in interface regions. The next, alternating optimisation, is a restriction of this technique in which mesh entities are only allowed to migrate between subdomains in one direction. The third treats the gain as a potential held and uses the concept of relative gain for selecting approp riate vertices to migrate. The results are compared and seen to produce ver y high global quality partitions, very rapidly. The results are also compar ed with another partitioning tool and shown to be of higher quality althoug h taking longer to compute. (C) 2000 Elsevier Science B.V. All rights reser ved.