Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Computational Science, Engineering & Technology Series
MESH PARTITIONING TECHNIQUES AND DOMAIN DECOMPOSITION METHODS
Edited by: F. Magoulès
Graph and Mesh Partitioning: An Overview of the Current State-of-the-Art
R. Baños Navarro and C. Gil Montoya
Department of Computer Architecture and Electronics, University of Almeria, Spain
R. Baños Navarro, C. Gil Montoya, "Graph and Mesh Partitioning: An Overview of the Current State-of-the-Art", in F. Magoulès, (Editor), "Mesh Partitioning Techniques and Domain Decomposition Methods", Saxe-Coburg Publications, Stirlingshire, UK, Chapter 1, pp 1-26, 2007. doi:10.4203/csets.17.1
Keywords: mesh partitioning, graph partitioning, load balancing, domain decomposition, VLSI design, heuristic methods, multi-constraint optimisation, multi-objective optimisation.
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.
purchase the full-text of this chapter (price £25)