Nested Dissection-based ordering

ND algorithm

ND is a serial ordering algorithm for graphs or sparse matrices that runs on the local graph for the node. ND computes a nested dissection based ordering recursively by computing edge separators and then computing a vertex cover based on the resulting boundary graph (from a bipartite matching of that boundary graph).

ND is currently an experimental method. In order to use, add "-D Zoltan2_ENABLE_Experimental:BOOL=ON" to cmake options.

Input

ND expects a Zoltan2::GraphModel object.

Parameters

In order to enable ND:

• order_method should be set to "nd"

The following parameters are used by the ND algorithm:

• num_global_parts – specifies the target number parts to use when computing the nested dissection ordering
• edge_separator_method (currently "rcb" or "phg") – partitiong method to use when calculating edge separator

Solution

An ND solution is a permutation, currently given as a list of local ids.

Source

Zoltan2_AlgND.hpp is the source file for ND.