Scotch Brand 5.1.10 - Manual (Page 18)

3.2.6 Graph separation methods
The core of our incomplete nested dissection algorithm uses graph separation
methods as black boxes. It allows the orderer to run any type of graph separation
method compatible with our criteria for quality, that is, reducing the size of the
vertex separator while maintaining the loads of the separated parts within some
user-specified tolerance. Separation jobs maintain an internal image of the current
vertex separator, indicating for every vertex of the job whether it is currently
assigned to one of the two parts, or to the separator. It is therefore possible to
apply several different methods in sequence, each one starting from the result of
the previous one, and to select the methods with respect to the job characteristics,
thus enabling the definition of separation strategies.
The currently implemented graph separation methods are listed below.
Fiduccia-Mattheyses
This is a vertex-oriented version of the original, edge-oriented, Fiduccia-
Mattheyses heuristics described in page 13.
Greedy graph growing
This is a vertex-oriented version of the edge-oriented greedy graph growing
algorithm described in page 14.
Multi-level
This is a vertex-oriented version of the edge-oriented multi-level algorithm
described in page 14.
Thinner
This greedy algorithm refines the current separator by removing all of the
exceeding vertices, that is, vertices that do not have neighbors in both parts.
It is provided as a simple gradient refinement algorithm for the multi-level
method, and is clearly outperformed by the Fiduccia-Mattheyses algorithm.
Vertex cover
This algorithm computes a vertex separator by first computing an edge sepa-
rator, that is, a bipartition of the graph, and then turning it into a vertex sep-
arator by using the method proposed by Pothen and Fang [48]. This method
requires the computation of maximal matchings in the bipartite graphs as-
sociated with the edge cuts, which are built using Duff’s variant [9] of the
Hopcroft and Karp algorithm [30]. Edge separators are computed by using a
bipartitioning strategy, which can use any of the graph bipartitioning methods
described in section 3.1.6, page 12.
4 Updates
4.1 Changes from version 4.0
Scotch has gone parallel with the release of PT-Scotch, the Parallel Threaded
Scotch . People interested in these parallel routines should refer to the PT-Scotch
and libScotch 5.1 User’s Guide [43], which extends this manual.
A compatibility library has been developed to allow users to try and use Scotch
in programs that were designed to use MeTiS. Please refer to Section 7.14 for more
information.
18