Dynamic load balancing through repartitioning is relatively straightforward. Any of the fast parallel graph partitioning algorithms of Section 3 may be employed. These include the parallel multilevel schemes. Algorithms that allow quick reordering of a refined or coarsened mesh through a slight shift of the original ordering, such as the index based algorithms of Section 3.3.3, can also be attractive due to their simplicity and data locality. For adaptive mesh based applications where the relationship between the ``parents'' and ``offspring'' elements is known, the octree partitioning approach [25,26] offers an efficient way of repartitioning. The tree representation (the octree) is used to form a one-dimensional list of elements, through a depth-first search. This list can be divided, in parallel, into segments to give nearly equal load. Members of the same segment tend to be spatially close to each other (because they are likely to have the same parent or parents close to each other), and thus form a good partition. This partition can be further smoothed [25] by migrating boundary elements based on a K-L like gain calculation. Incidentally a similar idea was used in the parallel generation of partitioned unstructured meshes [40], where a coarse background mesh was partitioned.
Standard graph partitioning algorithms however only have edge-cut as the sole objective. To minimize the data movement resulting from the repartitioning, a number of techniques have been used to modify the graph partitioning algorithms, so that the new partition is as close to an existing partitioning as possible. The idea of a virtual vertex was used in [81,19,37]. A virtual vertex is associated with each subdomain and is connected to each vertex in the subdomain by a virtual edge. The weight of this edge reflects the communication cost of migrating the vertex. By partitioning the combined graph, the dual objectives of minimizing edge-cut and data movement are considered at the same time. In [73], the idea of local matching was used where matchings were restricted to vertices that have the same home processor. This strategy biases the multilevel graph partitioner towards an existing partitioning, thus reducing data movement resulting from the repartitioning.
A re-mapping algorithm can be applied after the repartitioning to allocate the subdomains to the most appropriate processors, in order to reduce the data movement [5,65,72].