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

To order an unsymmetric matrix $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}\hfill {A}_{11}\hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill {S}_{1}\hfill \\ \hfill \hfill & \hfill {A}_{22}\hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill {S}_{2}\hfill \\ \hfill \hfill & \hfill \hfill & \hfill \dots \hfill & \hfill \hfill & \hfill \hfill & \hfill \dots \hfill \\ \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \dots \hfill & \hfill \hfill & \hfill \dots \hfill \\ \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill {A}_{KK}\hfill & \hfill {S}_{K}\hfill \end{array}\right).$$

Here $K$
is the user-deﬁned 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
${A}_{ii}$ are of
similar sizes.

The MC66 algorithm uses a multilevel approach combined with a Kernighan-Lin
type reﬁnement 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.