For more information about graph partitioning, see ParMetis.
Scotch is a library for ordering and partitioning, developed at LaBRI in Bordeaux, France. PT-Scotch is the parallel module in Scotch. (We use the name PT-Scotch when it applies only to parallel version, Scotch when it concerns at least the serial version.) Scotch is a third-party library in Zoltan and should be obtained separately from the Scotch web site. Currently, Zoltan supports version 5.1 of Scotch, compiled with the support of PT-Scotch and int coding for vertices, not long (on architectures where sizeof(int) != sizeof(long)).
If the parameter SCOTCH_TYPE is set to LOCAL and the number of processors is 1 (e.g., mpirun -np 1), the sequential version of Scotch is called.
Both the serial (Scotch) and the parallel (PT-Scotch) compute k-way partitioning by doing recursive bisection.
Scotch must be used in the context LB_APPROACH=partition, to balance poorly distributed data. Unlike ParMetis, Scotch doesn't support the multiconstraint partitioning feature. However, for single constraint partitioning it seems to produce better results than ParMetis although it requires less memory.
| Value of LB_METHOD: | GRAPH |
| Value of GRAPH_PACKAGE: | Scotch |
| Parameters: | |
| LB_APPROACH |
The load balancing approach:. PARTITION - partition from scratch, not taking the current data distribution into account |
| SCOTCH_METHOD | For now, always set to RBISECT |
| SCOTCH_STRAT | The Scotch strategy string; see the Scotch documentation. |
| SCOTCH_STRAT_FILE | A file that contains an arbitrary long Scotch strategy string; see the Scotch documentation. |
| SCOTCH_TYPE | Whether or not the parallel library is used. The default value is GLOBAL and if not set to LOCAL, the parallel graph partitioning is used. |
| CHECK_GRAPH | Level of error checking for graph input: 0 = no checking, 1 = on-processor checking, 2 = full checking. (CHECK_GRAPH==2 is very slow and should be used only during debugging). |
| SCATTER_GRAPH | Scatter graph data by distributing contiguous chunks of objects (vertices) of roughly equal size to each processor before calling the partitioner. 0 = don't scatter; 1 = scatter only if all objects are on a single processor; 2 = scatter if at least one processor owns no objects; 3 = always scatter. |
| GRAPH_SYMMETRIZE | How to symmetrize the graph:
NONE = graph is symmetric and no symmetrization is needed TRANSPOSE = if M is adjacency matrix of the input graph, output will be the graph representation of M+MT BIPARTITE = graph is symmetrized in a bipartite way : [[ 0 M ][Mt 0]] |
| GRAPH_SYM_WEIGHT | How edge weights are handled during symmetrization:
ADD = weights of each arc are added MAX = only the heaviest arc weight is kept See more informations about graph build options on this page |
| Default values: | |
| LB_APPROACH = Partition | |
| SCOTCH_METHOD = RBISECT | |
| SCOTCH_STRAT = "" (default Scotch strategy) | |
| SCOTCH_STRAT_FILE = "" (default Scotch strategy) | |
| CHECK_GRAPH = 1 | |
| SCATTER_GRAPH = 1 | |
| GRAPH_SYMMETRIZE = NONE | |
| GRAPH_SYM_WEIGHT = ADD | |
| Required Query Functions: | |
| ZOLTAN_NUM_OBJ_FN | |
| ZOLTAN_OBJ_LIST_FN | |
|
ZOLTAN_NUM_EDGES_MULTI_F
N or
ZOLTAN_NUM_EDGES_FN
ZOLTAN_EDGE_LIST_MULTI_F N or ZOLTAN_EDGE_LIST_FN |