----------------------------------------------------------------- Contents ----------------------------------------------------------------- (1) Introduction (2) Requirements (3) Installation (4) Using the Matlab interface (a) simple replacement for ichol (b) general interface (5) Control structure (6) Information structure ----------------------------------------------------------------- 1. Introduction ----------------------------------------------------------------- Given an n x n sparse symmetric matrix A, HSL_MI28 computes an incomplete Cholesky (IC) factorization LL' that may be used as a preconditioner when solving the system A * x = b using an iterative method. The IC factorization is based on a matrix decomposition of the form (L+R) (L+R)' + E, where the incomplete Cholesky factor L is a lower triangular matrix with positive diagonal entries. The matrix R is a strictly lower triangular and E is an error matrix. The matrix R has entries that are smaller in absolute value that those of L. It is used to stabilize the factorization process but is then discarded. The user can control the maximum number of entries within each column of L and R and the dropping of small entries from L and R. The matrix A is optionally reordered and/or scaled and, if necessary, shifted to avoid breakdown of the factorization. Thus an incomplete factorization of S Q' A S Q + alpha*I is computed, where S is a diagonal scaling matrix, Q is a permutation matrix and alpha is a positive shift. Further details are given in the Fortran user documentation and in the report: J.A. Scott and M. Tuma. (2013). HSL_MI28: an efficient and robust limited-memory incomplete Cholesky factorization code. Technical Report. RAL-P-2013-004. To appear in ACM Transactions on Mathematical Software (2014). ----------------------------------------------------------------- 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. ----------------------------------------------------------------- 3. Installation ----------------------------------------------------------------- Instructions for installing the Matlab Interface for HSL_MI28 are located in INSTALL. ----------------------------------------------------------------- 4. Using the Matlab interface ----------------------------------------------------------------- Two interfaces are offered: (a) hsl_mi28_ichol may be used as a replacement for the Matlab ichol (b) general interface that offers greater flexibility and more options than (a). In particular, A may optionally be preordered (this is not offered by (a)). Note that if (b) is used with default settings, A is preordered (see control.iorder in Section 6) and, in this case, (a) and (b) will return different results; the results will be the same if control.iorder is set to 0 (with all other components of control set to their defaults). ----------------------------------------------------------------- 4(a). Using the Matlab interface : the replacement for ichol ----------------------------------------------------------------- - If not already in the search paths, add the directory where you installed the interface to the search paths, e.g. >> addpath('mi28_matlab') >> javaaddpath('mi28_matlab') where mi28_matlab is the directory. [ You can add these paths permanently (see 'help pathtool')] - To compute an incomplete Cholesky factorization >> L = hsl_mi28_ichol(A) Options may be specified using a control structure (see Section 5) >> L = hsl_mi28_ichol(A,control) ----------------------------------------------------------------- 4(a)(i). Using the Matlab interface: replacement for ichol: example ----------------------------------------------------------------- Below is an example of using the interface that is a replacement for ichol (with default controls) in conjunction with an iterative solver: >> A = gallery('poisson',20,20); >> b = ones(length(A),1); >> L = hsl_mi28_ichol(A); >> x = pcg(A,b,1e-8,100,L,L'); ----------------------------------------------------------------- 4(b). Using the Matlab interface : the general interface ----------------------------------------------------------------- - If not already in the search paths, add the directory where you installed the interface to the search paths, e.g. >> addpath('mi28_matlab') >> javaaddpath('mi28_matlab') where mi28_matlab is the directory. [ You can add these paths permanently (see 'help pathtool')] - An incomplete factorization of A is computed using hsl_mi28_precond: >> pc = hsl_mi28_precond(A) Optionally, a control structure (see Section 5) may be used: >> pc = hsl_mi28_precond(A,control) hsl_mi28_precond returns a preconditioner object pc. Information about the constructed preconditioner is available by examining properties of pc, see Section 6 for details. - The preconditioner is applied to a (full) vector z and a vector y returned as follows: >> y = pc.apply(z) The preconditioner may be applied multiple times. - The memory associated with the preconditioner is freed when the object ceases to exist. To force this to occur, the clear command may be used: >> clear pc ----------------------------------------------------------------- 4(b)(i). Using the Matlab interface: general interface: example ----------------------------------------------------------------- Below is an example of using the Matlab interface with default controls: >> A = gallery('poisson',20,20); >> pc = hsl_mi28_precond(A); >> z = ones(length(A),1); >> y = pc.apply(z); >> clear pc; The interface may also be used in conjunction with an iterative solver: >> A = gallery('poisson',20,20); >> b = ones(length(A),1); >> pc = hsl_mi28_precond(A); >> x = pcg(A,b,1e-8,100,@pc.apply); >> clear pc; ----------------------------------------------------------------- 5. 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. Further details of the control components are given in the Fortran documentation. control.lsize and control.rsize : control the number of entries in L and R. The number of fill entries in each column of L is at most lsize and the number of entries in each column of R is at most rsize. In general, increasing lsize and/or rsize increases the quality of the preconditioner but at the cost of more work (slower factorize and precondition times) and the use of more memory. The default values are 20. control.alpha : holds the initial shift alpha. The default value is 0. control.iorder : controls whether A is preordered before the factorization. Options for the general interface are: <=0 : no ordering. 1 : reverse Cuthill-McKee (RCM) ordering. 2 : approximate minimum degree (AMD) ordering. 4 : the rows are ordered by ascending degree. 5 : METIS (nested dissection) ordering. 6 : Sloan profile reduction ordering. All other values are treated as 6. The default value is 6. For the ichol replacement interface, no preordering is offered (that is, all values are treated as 0). control.iscale : controls whether A is to be scaled before the factorization. Options are: <=0 : no scaling. 1 : scaling using l_2-norm of the columns of A. 2 : MC77 (1 iteration in inf norm, 3 iteration in one norm). 3 : MC64 Bipartite matching based scaling. 4 : Diagonal scaling. All other values are treated as 1. The default value is 1. control.lowalpha : controls the choice of the first non-zero shift in the event of factorization breakdown. The default value is 0.001. control.maxshift : controls the maximum number of times the shift can be decreased after a successful factorization with a positive shift. The default value is 3. control.shift_factor : controls how rapidly the shift is increased after a breakdown. The default value is 2. control.shift_factor2 : controls how rapidly the shift is decreased after a successful factorization with a positive shift. The default value is 4. control.small : any pivot whose modulus is less than small is treated as 0.0 and, if such a pivot is encountered, the factorization breaks down, the shift is increased and the factorization restarted. The default value is 1e-20. control.tau1 and control.tau2 : control the dropping of small entries from L and R. Dropping entries leads to sparser factors but may reduce the quality of the preconditioner. The default values are 0.001 and 0.0001, respectively ----------------------------------------------------------------- 6. Information available to user ----------------------------------------------------------------- The following properties of the computed preconditioner may be queried by the user: pc.alpha - Holds global shift used. pc.nzl - Number of entries in the computed incomplete factor L. pc.nzr - Number of entries in R. pc.nshift - Number of non-zero shifts used. pc.nrestart - Number of times the factorization was restarted.