for it to account for topological structures of the graph that would else be of
a too high level for it to encompass in its local optimization process.
3.1.7
Mapping onto variable-sized architectures
Several constrained graph partitioning problems can be modeled as mapping the
problem graph onto a target architecture, the number of vertices and topology of
which depend dynamically on the structure of the subgraphs to bipartition at each
step.
Variable-sized architectures are supported by the DRB algorithm in the follow-
ing way: at the end of each bipartitioning step, if any of the variable subdomains
is empty (that is, all vertices of the subgraph are mapped only to one of the sub-
domains), then the DRB process stops for both subdomains, and all of the vertices
are assigned to their parent subdomain; else, if a variable subdomain has only one
vertex mapped onto it, the DRB process stops for this subdomain, and the vertex
is assigned to it.
The moment when to stop the DRB process for a specific subgraph can be con-
trolled by defining a bipartitioning strategy that tests for the validity of a criterion
at each bipartitioning step, and maps all of the subgraph vertices to one of the
subdomains when it becomes false.
3.2
Sparse matrix ordering by hybrid incomplete nested dis-
section
When solving large sparse linear systems of the form
Ax
=
b
, it is common to
precede the numerical factorization by a symmetric reordering. This reordering is
chosen in such a way that pivoting down the diagonal in order on the resulting
permuted matrix
P AP
T
produces much less fill-in and work than computing the
factors of
A
by pivoting down the diagonal in the original order (the fill-in is the
set of zero entries in
A
that become non-zero in the factored matrix).
3.2.1
Minimum Degree
The minimum degree algorithm [55] is a local heuristic that performs its pivot
selection by iteratively selecting from the graph a node of minimum degree.
The minimum degree algorithm is known to be a very fast and general purpose
algorithm, and has received much attention over the last three decades (see for
example [1, 16, 39]). However, the algorithm is intrinsically sequential, and very
little can be theoretically proved about its efficiency.
3.2.2
Nested dissection
The nested dissection algorithm [17] is a global, heuristic, recursive algorithm which
computes a vertex set
S
that separates the graph into two parts
A
and
B
, ordering
S
with the highest remaining indices. It then proceeds recursively on parts
A
and
B
until their sizes become smaller than some threshold value. This ordering guarantees
that, at each step, no non zero term can appear in the factorization process between
unknowns of
A
and unknowns of
B
.
Many theoretical results have been carried out on nested dissection order-
ing [7, 38], and its divide and conquer nature makes it easily parallelizable. The
main issue of the nested dissection ordering algorithm is thus to find small vertex
separators that balance the remaining subgraphs as evenly as possible. Most often,
15
