Zoltan Developer's Guide  |  Previous

Appendix: Handling Degenerate Geometries

The geometry processed by one of the geometric methods RCB, RIB, or HSFC may be degenerate. By this we mean it may have 3-dimensional coordinates but be essentially flat, or it may have 3 or 2-dimensional coordinates but be essentially a line in space. If we treat the geometry as a lower dimensional object for the purpose of partitioning, the result may be a more natural partition (one the user would have expected) and a faster run time.

The caller may set the REDUCE_DIMENSIONS parameter to TRUE in any of the three geometric methods if they want Zoltan to check for a degenerate condition and do lower dimensional partitioning if such a condition if found. They may set the DEGENERATE_RATIO to specify how flat or thin a geometry must be to be considered degenerate.

Outline of Algorithm

All three geometric methods call Zoltan_Get_Coordinates to obtain the problem coordinates. If REDUCE_DIMENSIONS is TRUE, we check in this function to see if the geometry is degenerate. If it is, we transform the coordinates to the lower dimensional space, flag that the problem is now lower dimensional, and return the transformed coordinates. The RCB, RIB, or HSFC calculation is performed on the new coordinates in the lower dimensional space.

If KEEP_CUTS is TRUE, the transformation is saved so that in Zoltan_LB_Box_Assign or Zoltan_LB_Point_Assign the coordinates can be transformed before the assignment is calculated. If RCB_REUSE is TRUE in the RCB method, the transformation is also saved. On re-partitioning, we can do some simple tests to see if the degeneracy condition has changed before completely re-calculating the coordinate transformation.

To determine if the geometry is degenerate, we calculate the same inertial matrix that is calculated for RIB, except that we ignore vertex weights. The 3 orthogonal eigenvectors of the inertial matrix describe the three primary directions of the geometry. The bounding box oriented in these directions is tested for degeneracy. In particular (for a 3 dimensional geometry) if the length of the longest side divided by the length of the shortest side exceeds the DEGENERATE_RATIO, we consider the geometry to be flat. If in addition, the length longest side divided by the length of the middle side exceeds the DEGENERATE_RATIO, we consider the geometry to be essentially a line.

If a 3 dimensional geometry is determined to be flat, we transform coordinates to a coordinate system where the XY plane corresponds to the oriented bounding box, and project all coordinates to that plane. These X,Y coordinates are returned to the partitioning algorithm, which performs two dimensional partitioning. Similarly if the geometry is very thin, we transform coordinates to a coordinate system with the X axis going through the bounding box in it's principal direction, and project all points to that axis. Then one dimensional partitioning is performed.

There is a small problem in calculating Zoltan_LB_Box_Assign when the partitioning was performed on transformed geometry. The caller provides the box vertices in problem coordinates, but the partition was calculated in transformed coordinates. When the vertices are transformed, they are in general no longer the vertices of an axis-aligned box in the new coordinate system. The Box_Assign calculation requires an axis-aligned box, and so we use the bounding box of the transformed vertices. The resulting list of processes or parts intersecting the box may therefore contain some processes or parts which actually do not intersect the box in problem coordinates, however it will not omit any.

Data Structure Definitions

The transformation is stored in a Zoltan_Transform_Struct structure which is defined in zz/zz_const.h. It is saved as part of the algorithm specific information stored in the LB.Data_Structure field of the Zoltan_Struct. The flag that indicates whether the geometry was found to be degenerate is the Target_Dim field of this structure.

To use the degenerate geometry detection capability from a new geometric method, you would add a Zoltan_Transform_Struct structure to the algorithm specific data structure, add code to Zoltan_Get_Coordinates to look for it, and check the Target_Dim field on return to see if the problem dimension was reduced. You would also need to include the coordinate transformation in your Box_Assign and Point_Assign functionality.
 
 


[Table of Contents  |  Previous:  Hibert Space Filling Curve (HSFC)  |  Privacy and Security]