(3M) Calculator User Manual

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 ﬁrst subdomain, until half of the total we ight ha s been

processed. Remaining vertices are then allocated to the second subdo main.

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 Georg e 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 ra ndom, and repeatedly

adding vertices to this growing subset, such that ea ch 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 fashio n) diﬀerent 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, 3 1] and

should be considered as a strategy rather than as a method since it uses other

methods as parameters, repe atedly reduces the size of the graph to bipartition

by ﬁnding 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 proces s. 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 re ﬁnement, respectively.

tion with the Fiduccia-Mattheyses metho d to compute the initial partitions

and reﬁne the projected partitions at every level, usually leads to a signiﬁ-

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