As we have seen in the discussion of the RSB
algorithm (equation (6)), an
undirected graph can be uniquely represented
by an matrix, where the entry
is nonzero
if vertices
and
are connected by an edge and zero if the two
vertices are not connected. A good bisection of the graph is equivalent to
an ordering, through symmetric permutation,
of the matrix such that the resulting matrix
has very few nonzero off-diagonal entries corresponding to
the two principal diagonal blocks of size
.
This is because the off-diagonal entries correspond to the edges
between the two subdomains. Although such an ordering algorithm
is not readily available, there are a number of
algorithms that order the matrix
to minimize its bandwidth.
A partitioning algorithm [58] was suggested which
orders the vertices of the graph using matrix
ordering algorithms, and partitions the graph by taking the
first
vertices as the first subdomain, etc..
The algorithm is inexpensive and can usually result in
a smaller number of neighbors for each processor.
The edge-cut can be improved if the algorithm is
used recursively as a bisection algorithm.
Nonetheless in terms of edge-cut its is not
as good as algorithms such as the RSB or the greedy algorithm
[30].