The domain decomposition method embodies large potentials for a parallelization of FEM methods. The subdomains are assigned to processors that calculate the corresponding part of the approximation. Unfortunately, this mapping problem is NP-complete and there exist almost no efficient sequential or parallel heuristics that solve this problem sufficiently. For the special application of partitioning FEM-meshes heuristics have to be flexible with respect to the measures they optimize.
Graph partitioning in general is a combinatorial optimization problem.
This makes sense in order to reduce the amount of necessary communication of the parallel FEM-simulation. But there are several other measures that are often much more important than cut size and that depend very much on the numerical solution method used for the simulation. Examples are the aspect ratio of subdomains or their convexity. We describe some of the most common partitioning heuristics as well as new developments in the area of decomposing FEM meshes.