Version 2.2.1
20th September 2022 User documentation
 Recent Changes

Code Download
 Single
 Double
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 userdefined number of blocks. The aim is to minimize the size of the border in the above matrix, also known as the netcut, 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 KernighanLin type refinement algorithm. Full details are discussed in Hu, Maguire and Blake, Computers and Chemical Engrg. 21 (2000), pp.16311647.
MC66
may be used to preorder an unsymmetric matrix for use with the sparse matrix solver HSL_MP43
.