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*.

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