Reducing the bandwidth of the matrix

As we have seen in the discussion of the RSB algorithm (equation (6)), an undirected graph can be uniquely represented by an $n\times n$ matrix, where the entry $(i,j)$ is nonzero if vertices $i$ and $j$ 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 ${n\over 2} \times {n\over 2}$. 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 $n/p$ 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].