Zoltan User's Guide  |  Next  |  Previous

Nested Dissection by Scotch

Nested Dissection is a popular method to compute fill-reducing orderings for graphs and sparse matrices. It can also be used for other ordering purposes. The algorithm recursively finds a separator (bisector) in a graph, orders the nodes in the two subsets first, and nodes in the separator last.

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 names Scotch and PT-Scotch interchangeably.) Scotch is a third-party library in Zoltan and should be obtained separately from the Scotch web site. Zoltan supports version 5.1 of Scotch.

If the parameter ORDER_METHOD is set to SCOTCH, the sequential version of Scotch is called. If the parameter ORDER_METHOD is set to PTSCOTCH, the parallel version of Scotch (PT-Scotch) is called.

Order_Method String: PTSCOTCH or SCOTCH
Parameters:
   SCOTCH_METHOD For now, always set to NODEND
   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.
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


[Table of Contents  | Next:  Local Ordering with HSFCPrevious:  Ordering by ParMetis  |  Privacy and Security]