----------------------------------------------------------------- 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)