### HSL_MC64 Permute and scale a sparse unsymmetric or rectangular matrix to put
large entries on the diagonal

Given a sparse unsymmetric or rectangular matrix
$A$ =
${\left\{{a}_{ij}\right\}}_{m\times n}$,
$m\ge n$, this
subroutine attempts to ﬁnd a row and column permutation that makes the permuted matrix
have $n$
entries on its diagonal. If the matrix is structurally nonsingular, the subroutine
optionally returns a permutation that maximizes the smallest element on the
diagonal, maximizes the sum of the diagonal entries, or maximizes the product
of the diagonal entries of the permuted matrix. For the latter option, the
subroutine also ﬁnds scaling factors that may be used to scale the original
matrix so that the nonzero diagonal entries of the permuted and scaled matrix
are one in absolute value and all the oﬀ-diagonal entries are less than or
equal to one in absolute value. The natural logarithms of the scaling factors
${u}_{i}$,
$i=1,...,n$, for the
rows and ${v}_{j}$,
$j=1,...,n$,
for the columns are returned so that the scaled matrix
$B$ =
${\left\{{b}_{ij}\right\}}_{n\times n}$ has
entries

$${b}_{ij}={a}_{ij}exp\left({u}_{i}+{v}_{j}\right).$$

In this Fortran 95 version, there are added facilities from the original MC64 code
for working on rectangular and symmetric matrices. For the rectangular case, a row
and column permutation are returned so that the user can permute the matching
to the diagonal and identify the rows in the structurally nonsingular block. For the
symmetric case, the user must only supply the lower triangle and, if a scaling is
computed, it will be a symmetric scaling with the same property as in the
unsymmetric case. Structually non-singular matrices are supported using the
maximum product matching only.