HSL_MC66: Permute an unsymmetric sparse matrix to singly bordered blocked diagonal form

To order an unsymmetric matrix \(\mathbf{A}\) into singly bordered blocked diagonal (SBBD) form. Given the sparsity pattern of a matrix, this routine generates a row and column ordering that can be used to reorder the matrix into the following SBBD form:

\[\left ( \begin{array}{cccccc} \mathbf{A} _{11} &&&&& \mathbf{S} _1 \\ & \mathbf{A} _{22} &&&& \mathbf{S} _2 \\ && \ldots &&& \ldots \\ &&& \ldots && \ldots \\ &&&&\mathbf{A} _{KK} & \mathbf{S} _K \end{array} \right ) .\]

Here \(K\) is the user-defined number of blocks. The aim is to minimize the size of the border in the above matrix, also known as the net-cut, and to achieve load balance by ensuring that the rectangular matrices \(\mathbf{A} _{ii}\) are of similar sizes.

The MC66 algorithm uses a multilevel approach combined with a Kernighan-Lin type refinement algorithm. Full details are discussed in Hu, Maguire and Blake, Computers and Chemical Engrg. 21 (2000), pp.1631-1647.

MC66 may be used to preorder an unsymmetric matrix for use with the sparse matrix solver HSL_MP43.