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

Version 2.2.0

13th February 2014

User documentation

Fortran

Single
Double

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:

(\begin{matrix} A_{11} & S_{1} \\ A_{22} & S_{2} \\ \dots & \dots \\ \dots & \dots \\ A_{K K} & S_{K} \end{matrix}) .

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_{i i}$ 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.