NPAC Technical Report SCCS-476
An Object Oriented Recursive Bisection Algorithm for the CM-5
Gregor von Laszewski
Submitted April 16 1993
Abstract
Recursive bisection is a very fast partitioning strategy. It
is often used for dividing points in a two dimensional plane into a
number of partitions containing an approximately equal number of
points. The membership of a point to a specific partition is
specified by its location in the two dimensional plane. This scheme
can be generalized in two ways.
First, the bisection algorithm can be expanded to
multidimensional planes.
Second, the algorithm can be used on any plane for which
a linear order between the elements is defined.
This report presents an object-oriented approach using a multi
dimensional recursive bisection algorithm on a distributed memory
architecture. By specifying the number of planes and their linear
order for each plane a variety of real problems can be solved with
minimum effort.
Results for partitioning two dimensional planes on the CM5 are
given.