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.
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.
The main routine for RIB is Zoltan_RIB in the file rcb/rib.c.