(3M) Calculator User Manual

levl
The level of the s ubgraph in the separators tree, starting from zero
at the r oot of the tree. Integer.
proc
The number of processors on which the current subgraph is dis-
tributed at this level of the separators tree. This variable is available
only when calling from routines of the PT-Scotch parallel library.
Integer.
rank
The rank of the current processor among the group of processors
on which the current subgraph is distributed at this level of the
separators tree. This variable is available only when calling from
routines of the PT-Scotch parallel library, for instance to decide
which node separation strategy should be used on which processor
in a multi-sequential approach. Integer.
vert
The number of vertices of the current s ubgraph. Integer.
The currently available vertex separation methods are the following.
b Band method. Available only fo r graph separation strategies. This metho d
builds a band graph of given width around the current separator of the graph
to which it is applied, a nd calls a g raph separation strategy to re fine the
equivalent separator of the ba nd graph. Then, the refined separator of the
band graph is projected back to the current graph. This method, presented
in [8], was created to reduce the cost of sepa rator refinement algorithms in a
multi-level context, but it improves partition quality too. The parameters of
the band separation method are listed below.
bnd=st rat
Set the vertex separation strategy to be used on the band graph.
org=st rat
Set the fallback vertex separation strategy to be used on the original
graph if the band graph strategy could not be used. The three cases
which require the use of this fallback strategy are the following. First, if
the separator of the original graph is empty, which makes it impossible
to compute a band graph. Second, if any part of the band graph to be
built is of the same size as the one of the original graph. Third, if the
application of the bnd vertex separation method to the band graph leads
to a situation where bo th anchor vertices are placed in the same part.
width=val
Set the width of the band graph. All graph vertices that are at a distance
less than or equal to val from any separator vertex are kept in the band
graph.
e Edge-separation method. Available only for graph separation strategies. This
method builds vertex separators from edge separators, by the method pro-
posed by Pothen and Fang [48], which uses a variant of the Hopcroft and
Karp algorithm due to Duff [9]. This method is expensive and most often
yields poorer results than direct vertex-oriented methods such as the vertex
vertex Greedy-graph- growing and the vertex Fiduccia-Mattheyses algorithms.
The parameters of the edge-separation method are listed below.
67