###
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`

.