Zoltan Developer's Guide  |  Next  |  Previous

Appendix: Recursive Inertial Bisection (RIB)

Outline of Algorithm

The implementation of Recursive Inertial Bisection (RIB) in Zoltan is due due to Bruce Hendrickson and Robert Leland of Sandia National Laboratories for use in Chaco and was modified by Courtenay Vaughan. RIB is an algorithm similar to RCB (see the appendix on RCB for a description of RCB) in that it uses the coordinates of the objects to be balanced to do the load balancing. Similarly to RCB, the domain is recursively divided into two pieces until the number of subdomains needed is reached. In each stage of the division, the direction of the principle axis of the domain to be divided is calculated by determining an eigenvector of the inertial matrix. This direction vector is used to define a normal to a plane which is used to divide the domain into two pieces. This process is repeated until the desired number of subdomains is reached.

The communication of objects being divided is handled by the same routine as is used by RCB. For applications which wish to add more objects to the decomposition at a later time (e.g., through Zoltan_LB_Box_Assign or Zoltan_LB_Point_Assign), information to do this can be retained during the decomposition phase. This information is kept if the parameter KEEP_CUTS is set during the decomposition. The process is similar to that used for RCB, but the information kept is different. For each RIB cut, the center of mass of the subdomain which is cut, the direction vector, and a distance from the center of mass to the cutting plane have to be saved.

Data Structure Definitions

There are three major data structures in RIB and they are defined in rcb/rib.h and rcb/shared.h. The points which are being load balanced are represented as a structure Dot_Struct which contains the location of the point, its weight, and the originating processor's number. The nodes on the decomposition tree are represented by the structure rib_tree which contains the position of the cut, the center of mass of the subdomain which is being cut, the direction vector of the principle axis of the subdomain, and the node's parent and two children (if they exist) in the tree. The structure RIB_Struct is the RIB data structure which holds pointers to all of the other data structures needed for RIB. It contains an array of Dot_Struct to represent the points being load balanced, global and local IDs of the points, an array of rib_tree (whose length is the number of processors) which contains the decomposition tree, and the dimension of the problem.


The parameters used by RIB and their default values are described in the RIB section of the Zoltan User's Guide. These can be set by use of the Zoltan_RIB_Set_Param subroutine in the file rcb/rib.c.

When the parameter REDUCE_DIMENSIONS is specified, the RIB algorithm will perform lower dimensional partitioning if the geometry is found to be degenerate. More information on detecting degenerate geometries may be found in another section.

Main Routine

The main routine for RIB is Zoltan_RIB in the file rcb/rib.c.

[Table of Contents  |  Next:  ParMETIS and Jostle  |  Previous:  Recursive Coordinate Bisection (RCB)  |  Privacy and Security]