The recursive coordinate
bisection (RCB) algorithm [87] partitions
the graph according to the coordinates of the vertices.
For this purpose the coordinate of a vertex of the communication graph
is taken as that of its corresponding node of the mesh, or
that of the centroid of the corresponding element in the case of a dual graph.
The RCB algorithm divides the graph into two halves according to the
-coordinates of the vertices, then further into four according to the
-coordinates, etc.. This works well when the mesh is evenly spread
over a simple domain. Otherwise it can create long boundaries with disconnected
subdomains. This situation can be alleviated by the so called
unbalanced recursive bisection approach [46], where instead of
dividing the vertices into equal sets, one chooses the partitioning
that minimizes the aspect ratio and divides the graph into
subgraphs of
and
vertices respectively. Here
is the
number of vertices in the graph,
the number of processors and
By suitable choice of
at each bisection,
this approach
leads to subdomains of equal number of vertices but with better aspect ratios.
Figure 3 shows the result of applying the RCB to the dual graph of a mesh with 788 elements. It creates 142 inter-boundary edges.