Multi-jagged algorithm

Multi-jagged (MJ) is a parallel (MPI+OpenMP) geometric partitioning algorithm that is a generalization of the recursive coordinate bisection algorithm. MJ partitions the coordinates into "p" balanced parts. Partitioning continues recursively in each part until the desired number of balanced parts has been created. The number of partitions in each level of recursion need not be the same.

Coordinates can be weighted, in which case the total weight in each part is balanced, rather than the number of coordinates in each part.

Input

MJ expects a Zoltan2::CoordinateInput object. This class supports geometric coordinates of arbitrary dimension, with weights of arbritrary dimension. If weights are not provided, MJ assumes coordinates are equally weighted.

Parameters

In order to enable MJ:

algorithm should be set to "multijagged"

The following parameters are used by the MJ algorithm:

imbalance_tolerance (default is 1.0001 )
mj_parts (default is none )
rectilinear_blocks (default is yes )
mj_recursion_depth (default is coordinate dimension )
mj_enable_rcb (default is 0 )
mj_concurrent_part_count (default is 1)

Solution

An MJ solution is a list of global IDs with a corresponding list of part numbers and process ranks.

Quality measures

MJ quality is measured with an imbalance measure. Use the parameter compute_metrics if you want the Zoltan2::PartitioningProblem to compute imbalance metrics for the solution.

Examples

See MultiJaggedTest.cpp for an example of using the MJ algorithm.

Source

Zoltan2_AlgMultiJagged.hpp is the source file for MJ.