** Next:** Model Description
**Up:** Related Research
** Previous:** Generation of Meshes in Parallel

##

Mesh Partitioning

The mesh partitioning is motivated by the fact that the domain
decomposition provides a natural route to parallelism. An automatic
mesh decomposer should distribute the mesh across the individual
processors so that the computational load is evenly balanced and the
amount of interprocessor communication is minimized. However, the
numerical experience has shown that several other issues, as the subdomain
shape and connectivity, in addition
to load balancing and communication costs, need to be addressed [87].
In recent years, a considerable attention
[21,33,50,69,84,87,102,134,167]
has been focused on developing suitable techniques to solve the mesh
partitioning problem and several powerful methods have been devised.
The greedy algorithm
[21,50] is based on a successive expansion
of a subdomain, initially formed by one appropriately chosen element,
until it comprises a sufficiently large number of elements. The expansion
is usually driven by neighbourhood search schemes using the
depth-first or breadth-first search. The basic
disadvantage of this very fast technique resides in the fact that
the final partitioning is often very far from the ``optimal''
one. However, the speed makes this technique very suitable for an initial
decomposition subjected to further optimization based, for example, on
the relative gain concept [167] or simulated
annealing [159].
The recursive bisection methods [102,159] utilize the spatial
distribution of a mesh. While the coordinate recursive bisection
(Cartesian, polar, or spherical) exploits only the dimensional properties of the
mesh with respect to a given coordinate system, the inertial
recursive bisection accounts for principal inertial properties of the mesh which
are invariant with respect to the coordinate system. The spectral
recursive bisection [69,84] is based on the
finding that the second largest eigenvalue of the Laplacian matrix of an
undirected graph associated with a mesh provides a good measure of
the connectivity of the mesh and that the components of the
corresponding eigenvector can be conveniently used for the mesh
bisection. Although this approach provides decomposition of a high
quality, computationally complexity makes its use problematic when
large meshes are under consideration. This deficiency was partially
eliminated by a multilevel implementation of this
technique [84].

** Next:** Model Description
**Up:** Related Research
** Previous:** Generation of Meshes in Parallel
*Daniel Rypl *

2005-12-07