----------------------------------------------------------------- 1. Introduction ----------------------------------------------------------------- HSL_MC80 computes a matching-based ordering for a sparse matrix A and optionally scaling factors based on the associated weighted matching. Such an ordering can significantly reduce the need for pivoting during an LDL^T factorization such as that computed by HSL_MA97. However, if pivoting is not required the factors L will be considerably denser than if a normal fill-reducing ordering were used. ----------------------------------------------------------------- 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 for HSL_MC80 are located in INSTALL. ----------------------------------------------------------------- 4. Using the Matlab interface ----------------------------------------------------------------- - If not already in the search paths, add the directory where you installed the interface to the search paths, e.g. >> addpath('mc80_matlab') >> javaaddpath('mc80_matlab') where mc80_matlab is the directory. [ You can add these paths permanently (see 'help pathtool') ] - To obtain a permutation that may be used to order the matrix A using matching-based AMD: >> order = hsl_mc80_order(A) The permtuation abs(order) is compatible with that returned from symamd(A). Negative values in order are used to indicate that the pivot can was matched as a 2x2 pivot, which can be exploited by some specialised linear solvers such as HSL_MA77. - A scaling may also be returned based on the weighted matching calculated: >> [order, scale] = hsl_mc80_order(A) - To obtain a permutation that may be used to order the matrix A using a specified matching-based ordering: >> order = hsl_mc80_order(A, type) or >> [order,scale] = hsl_mc80_order(A, type) where type is one of: 'amd' for approximate minimum degree, 'md' for minimum degree, or 'metis' for nested dissection using the MeTiS package (requires special compilation, see INSTALL). - To specify algorithmic parameters a control structure may be provided: >> order = hsl_mc80_order(A, type, control) or >> [order,scale] = hsl_mc80_order(A, type, control) The control structure is described in Section 5. - Finally an info structure may be requested containing algorithmic statistics: >> [order,scale,info] = hsl_mc80_order(A) or >> [order,scale,info] = hsl_mc80_order(A, type) or >> [order,scale,info] = hsl_mc80_order(A, type, control) The info structure is described in Section 5. ----------------------------------------------------------------- 5. Control and information structures ----------------------------------------------------------------- A limited subset of the Fortran control and information parameters may be used through the MATLAB interface as described below. ----------------------------------------------------------------- 5(a). The control structure ----------------------------------------------------------------- The argument control may have any of the following components set. If unrecognised components are present a warning is issued. If a component is not present its default value is used. control.unmatched_scale_zero - True or false. If true, scaling for unmatched rows and columns is set to zero, otherwise, if false, scaling is determined for these rows and columns such that all entries in the unmatched part of A have absolute value <= 1. Scaling unmatched rows and columns of A may accelerate a subsequent factorization, but may produce incorrect results if the matched submatrix is numerically singular. Default is false. control.unmatched_last - True or false. If true, unmatched rows columns are ordered in positions struct_rank+1, ... n. Otherwise, if false, unmatched columns are ordered in a position to minimize fill. The default is false. A fuller description for many of the components is available in the Fortran documentation. ----------------------------------------------------------------- 5(b). The info structure ----------------------------------------------------------------- On return from a routine, the output argument info is a structure that will the following components set: info.compress_rank - Order of the compressed matrix ordered. info.max_cycle - Length of shortest cycle in matching before splitting. info.struct_rank - Structural rank of A. A fuller description for many of the components is available in the Fortran documentation. ----------------------------------------------------------------- 6. Example ----------------------------------------------------------------- The following MATLAB session shows an example of using hsl_mc80 to order a trivial matrix. Observe that the final scaled and reordered matrix has large entries on the diagonal and all entries are less than or equal to one in absolute value. >> A = sparse ([1 1 1 2 2 3 3 3 4 4], [2 3 4 1 3 1 2 3 1 4], [1.1-i 2.2-i 3.3-i, 1.1+i 4.4-i, 2.2+i 4.4+i 5.5, 3.3+i 6.6]); >> full(A) ans = 0.0000 + 0.0000i 1.1000 - 1.0000i 2.2000 - 1.0000i 3.3000 - 1.0000i 1.1000 + 1.0000i 0.0000 + 0.0000i 4.4000 - 1.0000i 0.0000 + 0.0000i 2.2000 + 1.0000i 4.4000 + 1.0000i 5.5000 + 0.0000i 0.0000 + 0.0000i 3.3000 + 1.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 6.6000 + 0.0000i >> [order,scale,info] = hsl_mc80_order(A) order = -1 -4 -2 -3 scale = 0.7450 0.5197 0.4264 0.3892 info = compress_rank: 2 max_cycle: 2 struct_rank: 4 >> SAS = diag(scale) * A * diag(scale)'; % note: destroys sparsity, be careful! >> full(SAS) ans = 0.0000 + 0.0000i 0.4260 - 0.3872i 0.6989 - 0.3177i 0.9570 - 0.2900i 0.4260 + 0.3872i 0.0000 + 0.0000i 0.9751 - 0.2216i 0.0000 + 0.0000i 0.6989 + 0.3177i 0.9751 + 0.2216i 1.0000 + 0.0000i 0.0000 + 0.0000i 0.9570 + 0.2900i 0.0000 + 0.0000i 0.0000 + 0.0000i 1.0000 + 0.0000i >> full(SAS(abs(order), abs(order))) ans = 0.0000 + 0.0000i 0.9570 - 0.2900i 0.4260 - 0.3872i 0.6989 - 0.3177i 0.9570 + 0.2900i 1.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.4260 + 0.3872i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.9751 - 0.2216i 0.6989 + 0.3177i 0.0000 + 0.0000i 0.9751 + 0.2216i 1.0000 + 0.0000i