Coordinate bisection

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 $x$-coordinates of the vertices, then further into four according to the $y$-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 $nk/p$ and $n(p-k)/p$ vertices respectively. Here $n$ is the number of vertices in the graph, $p$ the number of processors and $k\in\{1,2,\ldots,p-1\}.$ By suitable choice of $k$ 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.

Figure 3: Partitioning a mesh into 16 subdomains using RCB