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) |
![]() |
(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].