Scotch Brand 5.1.10 - Manual (Page 13)

space that derives from the one which was globally defined at the coarsest
level, thus preventing local optimization refinement algorithms to be trapped
in local optima of the finer graphs [8].
Diffusion
This global optimization method, presented in [42], flows two kinds of antag-
onistic liquids, scotch and anti-scotch, from two source vertices, and sets the
new frontier as the limit between vertices which contain scotch and the ones
which contain anti-scotch. In order to add load-balancing constraints to the
algorithm, a constant amount of liquid disappears from every vertex per unit
of time, so that no domain can spread across more than half of the vertices.
Because selecting the source vertices is essential to the obtainment of use-
ful results, this method has been hard-coded so that the two source vertices
are the two vertices of highest indices, since in the band method these are
the anchor vertices which represent all of the removed vertices of each part.
Therefore, this method must be used on band graphs only, or on specifically
crafted graphs.
Exactifier
This greedy algorithm refines the current partition so as to reduce load imbal-
ance as much as possible, while keeping the value of the communication cost
function as small as possible. The vertex set is scanned in order of decreasing
vertex weights, and vertices are moved from one subdomain to the other if
doing so reduces load imbalance. When several vertices have same weight,
the vertex whose swap decreases most the communication cost function is se-
lected first. This method is used in post-processing of other methods when
load balance is mandatory. For weighted graphs, the strict enforcement of
load balance may cause the swapping of isolated vertices of small weight, thus
greatly increasing the cut. Therefore, great care should be taken when using
this method if connectivity or cut minimization are mandatory.
Fiduccia-Mattheyses
The Fiduccia-Mattheyses heuristics [12] is an almost-linear improvement of
the famous Kernighan-Lin algorithm [35]. It tries to improve the bipartition
that is input to it by incrementally moving vertices between the subsets of
the partition, as long as it can find sequences of moves that lower its commu-
nication cost. By considering sequences of moves instead of single swaps, the
algorithm allows hill-climbing from local minima of the cost function. As an
extension to the original Fiduccia-Mattheyses algorithm, we have developed
new data structures, based on logarithmic indexings of arrays, that allow us
to handle weighted graphs while preserving the almost-linearity in time of the
algorithm [44].
As several authors quoted before [24, 32], the Fiduccia-Mattheyses algorithm
gives better results when trying to optimize a good starting partition. There-
fore, it should not be used on its own, but rather after greedy starting methods
such as the Gibbs-Poole-Stockmeyer or the greedy graph growing methods.
Gibbs-Poole-Stockmeyer
This greedy bipartitioning method derives from an algorithm proposed by
Gibbs, Poole, and Stockmeyer to minimize the dilation of graph orderings,
that is, the maximum absolute value of the difference between the numbers of
neighbor vertices [18]. The graph is sliced by using a breadth-first spanning
13