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