-----------------------------------------------------------------
Contents
-----------------------------------------------------------------
(1) Introduction
(2) Requirements
(3) Installation
(4) Using the Matlab interface
-----------------------------------------------------------------
1. Introduction
-----------------------------------------------------------------
Given a sparse matrix A = a_{ij} of dimension m by n, HSL_MC64 attempts
to find both row and column permutations such that the permuted matrix
has n entries on its diagonal. If the matrix is structurally nonsingular,
the permutation may optionally maximize either
(a) the smallest entry on the diagonal,
(b) the sum of the diagonal entries, or
(c) the product of the diagonal entries
of the permuted matrix.
When (c) is chosen, scaling factors may optionally be returned such that
the scaled and permuted matrix has the following properties:
1. The nonzero diagonal entries are one in absolute value, and
2. All off-diagonal entries are less than or equal to one in absolute value.
The natural logarithms of the scaling factors u_{i}, i = 1,..,m, for the rows,
and v_{j}, j = 1,..,n, for the columns, are returned such that the scaled
matrix B = b_{ij} of dimension m by n has entries
b_{ij} = a_{ij}.exp(u_{i}+v_{j}).
For further details of the algorithm refer to either the Fortran user
documentation, or the journal article [1].
[1] I.S. Duff and J. Koster. The design and use of algorithms for permuting
large entries to the diagonal of sparse matrices. SIAM J. Matrix Analysis and
Applications 20 (1997), no.4, pp 889-901.
-----------------------------------------------------------------
2. Requirements
-----------------------------------------------------------------
These instructions should work on Linux, Mac OS or Windows systems.
They have been tested using the six most recent releases of Matlab.
Please note that HSL software requires a Fortran compiler to be installed
that is compatible with Matlab. Please see
https://uk.mathworks.com/support/requirements/supported-compilers.html
and look up the requirements for your OS and version of Matlab.
The MATLAB environment variable must point to your system Matlab directory
(see INSTALL for further details).
-----------------------------------------------------------------
3. Installation
-----------------------------------------------------------------
Instructions for installing the Matlab interface to HSL_MC64 are
located in INSTALL. You can type hsl_mc64_install without any
input arguments at the command line of Matlab to proceed to the
standard installation.
-----------------------------------------------------------------
4. Using the Matlab interface
-----------------------------------------------------------------
[perm_row,perm_col,info] = hsl_mc64(A) finds a permutation of A
given by the arrays perm_row and perm_col such that the smallest
value on the diagonal of the permuted matrix is maximized, using
a bottleneck bipartite algorithm. If A is retangular, it must have
more rows than columns (otherwise pass A'). The returned permutation
arrays perm_row and perm_col are such that A(perm_row,perm_col) is
the permuted matrix. The returned structure info has the following
components:
info.error indicates success (>=0) or failure (<0)
of the routine. Specific values are detailed below.
info.strucrank is the structural rank of the matrix (number of entries
on the diagonal of the permuted matrix).
[perm_row,perm_col,info] = hsl_mc64(A,job) finds a permutation
of A that depends on job. If job has the following values, then
HSL_MC64 aims to:
1 Maximize the number of diagonal entries
2 Maximize the smallest diagonal value (bottleneck bipartite algorithm)
3 Maximize the smallest diagonal value (threshold matching algorithm)
4 Maximize the sum of diagonal entries
5 Maximize the product of diagonal entries.
[perm_row,perm_col,info] = hsl_mc64(A,job,sym) finds a symmetric
permutation of A if sym=1. Only the lower triangular part of A should
be passed to hsl_mc64 (i.e. tril(A)). If sym!=1, the call is equivalent
to hsl_mc64(A,job).
[perm_row,perm_col,scale_row,scale_col,info] = hsl_mc64(A,5) and
[perm_row,perm_col,scale_row,scale_col,info] = hsl_mc64(A,5,sym)
find a permutation of A that maximizes the product of the diagonal
entries (as job=5), and additionally return row and column scaling
factors of the original matrix such that the scaled and permuted
matrix B has entries of absolute value one on the diagonal and
absolute value less than one elsewhere.
Possible values of info.flag:
-8 sym=1, but matrix has entries in upper triangle. Pass tril(A) instead.
-5 Failure on memory allocation
0 Success
+1 Matrix is structurally singular (fewer than n entries on diagonal)
+2 The returned scaling factors are large and may cause overflow when
used (job=5 only)