The * recursive spectral bisection* (RSB) algorithm
[68,75,87] is based on
the following consideration. Let each vertex of the
graph be assigned
a value of either 1 or , and let the value assigned to
vertex be denoted by . This creates a bisection of the
graph in which the vertices having value 1 form one subdomain and
those with value
form the other. The edge-cut for the bisection can be expressed as

where means that there is an edge connecting the vertices and . In order to keep the load balanced, each of the two subdomains is required to have the same number of vertices. Thus the sum of all the values associated with the vertices is zero, that is

The graph bisection problem
is equivalent to minimizing (2) subject to (3) with
taking the value of either 1 or . This is an integer
programming problem which is difficult to solve when the number of vertices
is large. Ignoring the integer constraints,
the quadratic (2) can be minimized subject to the linear constraint
(3) only. This gives a continuous minimization problem. But without
an extra constraint the solution is simply the vector of zeros.
Remembering that when all the variables take the value
1 or , the sum of the squares should be , the number of
vertices. This gives the extra constraint

The quadratic (2) can be written as

(5) |

Here deg is the degree of the vertex , defined in Section 2 as the number of edges connected with the vertex . The matrix satisfies with the vector of all ones. Applying the necessary condition for the constrained minimization problem gives

(7) |

The matrix is positive semi-definite with smallest eigenvalue and corresponding eigenvector . Clearly is not a solution to the problem since it does not satisfy the load balancing constraint (3). If the graph is connected, then it can be shown that the next smallest eigenvalue is positive [63]. The eigenvector associated with this eigenvalue satisfies (3) because it is orthogonal to the first eigenvector . It also satisfies (4) by proper scaling, and thus is the solution of the constrained minimization problem. This eigenvector (also called the Fiedler vector) gives a value to each vertex of the graph, and the graph can be bisected by separating those with smaller values from those with larger values. The procedure can then be repeated on each of the subdomains. This gives the RSB algorithm. In practice the RSB algorithm almost always gives connected subdomains if the original graph is connected, however there can be exceptions, as Figure 5 shows.

Figure 6 gives a simple graph and the eigenvector associated with the second smallest eigenvalue of the Laplacian. Here the values of the eigenvector are marked beside each vertex in brackets. Sorting the vertices based on the values of the eigenvector bisects the graph into two triangles, with the edge-cut of one.

To find the eigenvector corresponding to the second smallest eigenvalue, the Lanczos algorithm can be employed. This is an iterative algorithm which requires operations per iteration. The algorithm normally converges in iterations, with typically less than a few hundred. Thus the algorithm has a complexity of . However the Lanczos algorithm requires the storage of Lanczos vectors of length , unless the entire Lanczos recurrence is run through a second time in order to accumulate the eigenvector. An alternative algorithm [56] for finding the eigenvector is to solve the minimization problem (2) using the conjugate gradient algorithm, which requires the storage of only four vectors. This algorithm was only tested on regular grids.

Figure 7 shows the result of applying the RSB algorithm to the dual graph of the mesh with 788 elements, the partition has 108 shared edges, significantly fewer than the edge-cut of 142 generated by the RCB and RGB algorithms, although the RSB algorithm is far more expensive. In this case all of the subdomains are connected.

Two recursive spectral bisections do not necessarily generate an optimal quadri-section [76]. Direct quadri-section, even octa-section, using two or three eigenvectors of the Laplacian matrix has been explored [34]. Another interesting way of utilizing multiple eigenvectors is to treat them as spectral coordinates of the vertices. Using these coordinates in the context of inertia bisection can generate partitions of better quality than RSB [77].