Zoltan User's Guide  |  Next  |  Previous

Nested Dissection by METIS/ParMETIS

Nested Dissection (ND) is a popular method to compute fill-reducing orderings for 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. In METIS/ParMETIS, the recursion is stopped when the graph is smaller than a certain size, and some version of minimum degree ordering is applied to the remaining graph.

METIS computes a (local) ordering of the objects (currently only for serial runs), while ParMETIS performs a global ordering of all the objects. ParMETIS currently (version 3.1, supported by Zoltan) requires that the number of processors is a power of two.

If ORDER_METHOD=PARMETIS ParMETIS is called, but if it is METIS, METIS is called.
 
 
Order_Method String: METIS or PARMETIS
Parameters:
   See ParMETIS. Note that the PARMETIS options are ignored when METIS is called. 
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:  Ordering by PT-Scotch |  Previous:  Ordering Algorithms  |  Privacy and Security]