Scotch Brand 5.1.10 - Manual (Page 14)

tree rooted at a randomly chosen vertex, and this process is iterated by se-
lecting a new root vertex within the last layer as long as the number of layers
increases. Then, starting from the current root vertex, vertices are assigned
layer after layer to the first subdomain, until half of the total weight has been
processed. Remaining vertices are then allocated to the second subdomain.
As for the original Gibbs, Poole, and Stockmeyer algorithm, it is assumed that
the maximization of the number of layers results in the minimization of the
sizes –and therefore of the cocycles– of the layers. This property has already
been used by George and Liu to reorder sparse linear systems using the nested
dissection method [17], and by Simon in [54].
Greedy graph growing
This greedy algorithm, which has been proposed by Karypis and Kumar [31],
belongs to the GRASP (“Greedy Randomized Adaptive Search Procedure”)
class [36]. It consists in selecting an initial vertex at random, and repeatedly
adding vertices to this growing subset, such that each added vertex results
in the smallest increase in the communication cost function. This process,
which stops when load balance is achieved, is repeated several times in order
to explore (mostly in a gradient-like fashion) different areas of the solution
space, and the best partition found is kept.
Multi-level
This algorithm, which has been studied by several authors [4, 23, 31] and
should be considered as a strategy rather than as a method since it uses other
methods as parameters, repeatedly reduces the size of the graph to bipartition
by finding matchings that collapse vertices and edges, computes a partition
for the coarsest graph obtained, and projects the result back to the original
graph, as shown in Figure 3. The multi-level method, when used in conjunc-
Coarsening
phase
Uncoarsening
phase
Initial partitioning
Projected partition
Refined partition
Figure 3: The multi-level partitioning process. In the uncoarsening phase, the light
and bold lines represent for each level the projected partition obtained from the
coarser graph, and the partition obtained after refinement, respectively.
tion with the Fiduccia-Mattheyses method to compute the initial partitions
and refine the projected partitions at every level, usually leads to a signifi-
cant improvement in quality with respect to the plain Fiduccia-Mattheyses
method. By coarsening the graph used by the Fiduccia-Mattheyses method
to compute and project back the initial partition, the multi-level algorithm
broadens the scope of the Fiduccia-Mattheyses algorithm, and makes possible
14