Graph and Mesh Partitioning: An Overview of the Current State-of-the-Art
Department of Computer Architecture and Electronics, University of Almeria, Spain
Efficient partitioning methods are critical for developing efficient solutions in a large variety of applications. For example, large-scale scientific simulations on parallel computers require the allocation of finite element meshes among the processors such that the number of elements assigned to each processor and the number of contiguous elements assigned to different processors is as low as possible. Graph partitioning algorithms can be used to satisfy these conditions by first modelling the mesh with a graph, and then partitioning it into several sub-graphs which represent mesh decomposition. This study provides a description of this problem and the current state of the art in mesh and graph partitioning methods, including multi-constraint and multi-objective approaches. It also offers information on several public domain packages for graph and mesh partitioning.