Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

Chapter Contents
Chapter Introduction
NAG Toolbox

NAG Toolbox: nag_sparse_complex_herm_basic_solver (f11gs)

Purpose

nag_sparse_complex_herm_basic_solver (f11gs) is an iterative solver for a complex Hermitian system of simultaneous linear equations; nag_sparse_complex_herm_basic_solver (f11gs) is the second in a suite of three functions, where the first function, nag_sparse_complex_herm_basic_setup (f11gr), must be called prior to nag_sparse_complex_herm_basic_solver (f11gs) to set up the suite, and the third function in the suite, nag_sparse_complex_herm_basic_diag (f11gt), can be used to return additional information about the computation.
These three functions are suitable for the solution of large sparse complex Hermitian systems of equations.

Syntax

[irevcm, u, v, work, ifail] = f11gs(irevcm, u, v, wgt, work)
[irevcm, u, v, work, ifail] = nag_sparse_complex_herm_basic_solver(irevcm, u, v, wgt, work)
Note: the interface to this routine has changed since earlier releases of the toolbox:
 At Mark 22: lwork was removed from the interface

Description

nag_sparse_complex_herm_basic_solver (f11gs) solves the complex Hermitian system of linear simultaneous equations $Ax=b$ using either the preconditioned conjugate gradient method (see Hestenes and Stiefel (1952), Golub and Van Loan (1996), Barrett et al. (1994) and Dias da Cunha and Hopkins (1994)) or a preconditioned Lanczos method based upon the algorithm SYMMLQ (see Paige and Saunders (1975) and Barrett et al. (1994)).
For a general description of the methods employed you are referred to Description in nag_sparse_complex_herm_basic_setup (f11gr).
nag_sparse_complex_herm_basic_solver (f11gs) can solve the system after the first function in the suite, nag_sparse_complex_herm_basic_setup (f11gr), has been called to initialize the computation and specify the method of solution. The third function in the suite, nag_sparse_complex_herm_basic_diag (f11gt), can be used to return additional information generated by the computation during monitoring steps and after nag_sparse_complex_herm_basic_solver (f11gs) has completed its tasks.
nag_sparse_complex_herm_basic_solver (f11gs) uses reverse communication, i.e., nag_sparse_complex_herm_basic_solver (f11gs) returns repeatedly to the calling program with the argument irevcm (see Arguments) set to specified values which require the calling program to carry out a specific task: either to compute the matrix-vector product $v=Au$; to solve the preconditioning equation $Mv=u$; to notify the completion of the computation; or, to allow the calling program to monitor the solution. Through the argument irevcm the calling program can cause immediate or tidy termination of the execution. On final exit, the last iterates of the solution and of the residual vectors of the original system of equations are returned.
Reverse communication has the following advantages.
 1 Maximum flexibility in the representation and storage of sparse matrices. All matrix operations are performed outside the solver function, thereby avoiding the need for a complicated interface with enough flexibility to cope with all types of storage schemes and sparsity patterns. This applies also to preconditioners. 2 Enhanced user interaction: you can closely monitor the progress of the solution and tidy or immediate termination can be requested. This is useful, for example, when alternative termination criteria are to be employed or in case of failure of the external functions used to perform matrix operations.

References

Barrett R, Berry M, Chan T F, Demmel J, Donato J, Dongarra J, Eijkhout V, Pozo R, Romine C and Van der Vorst H (1994) Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods SIAM, Philadelphia
Dias da Cunha R and Hopkins T (1994) PIM 1.1 — the parallel iterative method package for systems of linear equations user's guide — Fortran 77 version Technical Report Computing Laboratory, University of Kent at Canterbury, Kent, UK
Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore
Hestenes M and Stiefel E (1952) Methods of conjugate gradients for solving linear systems J. Res. Nat. Bur. Stand. 49 409–436
Higham N J (1988) FORTRAN codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation ACM Trans. Math. Software 14 381–396
Paige C C and Saunders M A (1975) Solution of sparse indefinite systems of linear equations SIAM J. Numer. Anal. 12 617–629

Parameters

Note: this function uses reverse communication. Its use involves an initial entry, intermediate exits and re-entries, and a final exit, as indicated by the argument irevcm. Between intermediate exits and re-entries, all arguments other than irevcm and v must remain unchanged.

Compulsory Input Parameters

1:     $\mathrm{irevcm}$int64int32nag_int scalar
On initial entry: ${\mathbf{irevcm}}=0$, otherwise an error condition will be raised.
On intermediate re-entry: irevcm must either be unchanged from its previous exit value, or can have one of the following values.
${\mathbf{irevcm}}=5$
Tidy termination: the computation will terminate at the end of the current iteration. Further reverse communication exits may occur depending on when the termination request is issued. nag_sparse_complex_herm_basic_solver (f11gs) will then return with the termination code ${\mathbf{irevcm}}=4$. Note that before calling nag_sparse_complex_herm_basic_solver (f11gs) with ${\mathbf{irevcm}}=5$ the calling program must have performed the tasks required by the value of irevcm returned by the previous call to nag_sparse_complex_herm_basic_solver (f11gs), otherwise subsequently returned values may be invalid.
${\mathbf{irevcm}}=6$
Immediate termination: nag_sparse_complex_herm_basic_solver (f11gs) will return immediately with termination code ${\mathbf{irevcm}}=4$ and with any useful information available. This includes the last iterate of the solution and, for conjugate gradient only, the last iterate of the residual vector. The residual vector is generally not available when the Lanczos method (SYMMLQ) is used. nag_sparse_complex_herm_basic_solver (f11gs) will then return with the termination code ${\mathbf{irevcm}}=4$.
Immediate termination may be useful, for example, when errors are detected during matrix-vector multiplication or during the solution of the preconditioning equation.
Changing irevcm to any other value between calls will result in an error.
Constraint: on initial entry, ${\mathbf{irevcm}}=0$; on re-entry, either irevcm must remain unchanged or be reset to ${\mathbf{irevcm}}=5$ or $6$.
2:     $\mathrm{u}\left(:\right)$ – complex array
The dimension of the array u must be at least $\mathit{n}$
On initial entry: an initial estimate, ${x}_{0}$, of the solution of the system of equations $Ax=b$.
On intermediate re-entry: must remain unchanged.
3:     $\mathrm{v}\left(:\right)$ – complex array
The dimension of the array v must be at least $\mathit{n}$
On initial entry: the right-hand side $b$ of the system of equations $Ax=b$.
On intermediate re-entry: the returned value of irevcm determines the contents of v in the following way.
If ${\mathbf{irevcm}}=1$ or $2$, v must store the vector $v$, the result of the operation specified by the value of irevcm returned by the previous call to nag_sparse_complex_herm_basic_solver (f11gs)
If ${\mathbf{irevcm}}=3$, v must remain unchanged.
4:     $\mathrm{wgt}\left(:\right)$ – double array
The dimension of the array wgt must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,\mathit{n}\right)$
The user-supplied weights, if these are to be used in the computation of the vector norms in the termination criterion (see Description and Arguments in nag_sparse_complex_herm_basic_setup (f11gr)).
Constraint: if weights are to be used, at least one element of wgt must be nonzero.
5:     $\mathrm{work}\left(\mathit{lwork}\right)$ – complex array
lwork, the dimension of the array, must satisfy the constraint $\mathit{lwork}\ge {\mathbf{lwreq}}$, where lwreq is returned by nag_sparse_complex_herm_basic_setup (f11gr).
On initial entry: the array work as returned by nag_sparse_complex_herm_basic_setup (f11gr) (see also Arguments in nag_sparse_complex_herm_basic_setup (f11gr)).
lwork, the dimension of the array, must satisfy the constraint $\mathit{lwork}\ge {\mathbf{lwreq}}$, where lwreq is returned by nag_sparse_complex_herm_basic_setup (f11gr).
On intermediate re-entry: must remain unchanged.

None.

Output Parameters

1:     $\mathrm{irevcm}$int64int32nag_int scalar
On intermediate exit: has the following meanings.
${\mathbf{irevcm}}=1$
The calling program must compute the matrix-vector product $v=Au$, where $u$ and $v$ are stored in u and v, respectively.
${\mathbf{irevcm}}=2$
The calling program must solve the preconditioning equation $Mv=u$, where $u$ and $v$ are stored in u and v, respectively.
${\mathbf{irevcm}}=3$
Monitoring step: the solution and residual at the current iteration are returned in the arrays u and v, respectively. No action by the calling program is required. To return additional information nag_sparse_complex_herm_basic_diag (f11gt) can be called at this step.
On final exit: if ${\mathbf{irevcm}}=4$, nag_sparse_complex_herm_basic_solver (f11gs) has completed its tasks. The value of ifail determines whether the iteration has been successfully completed, errors have been detected or the calling program has requested termination.
2:     $\mathrm{u}\left(:\right)$ – complex array
The dimension of the array u will be $\mathit{n}$
On intermediate exit: the returned value of irevcm determines the contents of u in the following way.
If ${\mathbf{irevcm}}=1$ or $2$, u holds the vector $u$ on which the operation specified by irevcm is to be carried out.
If ${\mathbf{irevcm}}=3$, u holds the current iterate of the solution vector.
On final exit: if ${\mathbf{ifail}}={\mathbf{3}}$ or $-{\mathbit{i}}$, the array u is unchanged from the initial entry to nag_sparse_complex_herm_basic_solver (f11gs). If ${\mathbf{ifail}}={\mathbf{1}}$, the array u is unchanged from the last entry to nag_sparse_complex_herm_basic_solver (f11gs). Otherwise, u holds the last iterate of the solution of the system of equations, for all returned values of ifail.
3:     $\mathrm{v}\left(:\right)$ – complex array
The dimension of the array v will be $\mathit{n}$
On intermediate exit: if ${\mathbf{irevcm}}=3$, v holds the current iterate of the residual vector. Note that this is an approximation to the true residual vector. Otherwise, it does not contain any useful information.
On final exit: if ${\mathbf{ifail}}={\mathbf{3}}$ or ${\mathbf{0}}$, the array v is unchanged from the last entry to nag_sparse_complex_herm_basic_solver (f11gs). If ${\mathbf{ifail}}={\mathbf{1}}$, the array v is unchanged from the initial entry to nag_sparse_complex_herm_basic_solver (f11gs). If ${\mathbf{ifail}}={\mathbf{0}}$ or ${\mathbf{2}}$, the array v contains the true residual vector of the system of equations (see also Error Indicators and Warnings). Otherwise, v stores the last iterate of the residual vector unless the Lanczos method (SYMMLQ) was used and ${\mathbf{ifail}}\ge {\mathbf{5}}$, in which case v is set to $0.0$.
4:     $\mathrm{work}\left(\mathit{lwork}\right)$ – complex array
5:     $\mathrm{ifail}$int64int32nag_int scalar
On final exit: ${\mathbf{ifail}}={\mathbf{0}}$ unless the function detects an error (see Error Indicators and Warnings).

Error Indicators and Warnings

Errors or warnings detected by the function:

Cases prefixed with W are classified as warnings and do not generate an error of type NAG:error_n. See nag_issue_warnings.

${\mathbf{ifail}}=-i$
If ${\mathbf{ifail}}=-i$, parameter $i$ had an illegal value on entry. The parameters are numbered as follows:
1: irevcm, 2: u, 3: v, 4: wgt, 5: work, 6: lwork, 7: ifail.
It is possible that ifail refers to a parameter that is omitted from the MATLAB interface. This usually indicates that an error in one of the other input parameters has caused an incorrect value to be inferred.
W  ${\mathbf{ifail}}=1$
nag_sparse_complex_herm_basic_solver (f11gs) has been called again after returning the termination code ${\mathbf{irevcm}}=4$. No further computation has been carried out and all input data and data stored for access by nag_sparse_complex_herm_basic_diag (f11gt) have remained unchanged.
W  ${\mathbf{ifail}}=2$
The required accuracy could not be obtained. However, nag_sparse_complex_herm_basic_solver (f11gs) has terminated with reasonable accuracy: the last iterate of the residual satisfied the termination criterion but the exact residual $r=b-Ax$, did not. A small number of iterations have been carried out after the iterated residual satisfied the termination criterion, but were unable to improve on the accuracy. This error code usually implies that your problem has been fully and satisfactorily solved to within or close to the accuracy available on your system. Further iterations are unlikely to improve on this situation. You should call nag_sparse_complex_herm_basic_diag (f11gt) to check the values of the left- and right-hand side of the termination condition.
${\mathbf{ifail}}=3$
nag_sparse_complex_herm_basic_setup (f11gr) was either not called before calling nag_sparse_complex_herm_basic_solver (f11gs) or it returned an error. The arrays u and v remain unchanged.
W  ${\mathbf{ifail}}=4$
The calling program requested a tidy termination before the solution had converged. The arrays u and v return the last iterates available of the solution and of the residual vector, respectively.
W  ${\mathbf{ifail}}=5$
The solution did not converge within the maximum number of iterations allowed. The arrays u and v return the last iterates available of the solution and of the residual vector, respectively.
${\mathbf{ifail}}=6$
The preconditioner appears not to be positive definite. It is likely that your results are meaningless: both methods require a positive definite preconditioner (see also Description). However, the array u returns the last iterate of the solution, the array v returns the last iterate of the residual vector, for the conjugate gradient method only.
W  ${\mathbf{ifail}}=7$
The matrix of the coefficients appears not to be positive definite (conjugate gradient method only). The arrays u and v return the last iterates of the solution and residual vector, respectively. However, you should be warned that the results returned can be be in error.
W  ${\mathbf{ifail}}=8$
The calling program requested an immediate termination. However, the array u returns the last iterate of the solution, the array v returns the last iterate of the residual vector, for the conjugate gradient method only.
${\mathbf{ifail}}=9$
The matrix appears to be singular.
${\mathbf{ifail}}=10$
User-supplied weights are to be used, but all elements of the array wgt are zero.
${\mathbf{ifail}}=-99$
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.

Accuracy

On completion, i.e., ${\mathbf{irevcm}}=4$ on exit, the arrays u and v will return the solution and residual vectors, ${x}_{k}$ and ${r}_{k}=b-A{x}_{k}$, respectively, at the $k$th iteration, the last iteration performed, unless an immediate termination was requested and the Lanczos method (SYMMLQ) was used.
On successful completion, the termination criterion is satisfied to within the user-specified tolerance, as described in Description in nag_sparse_complex_herm_basic_setup (f11gr). The computed values of the left- and right-hand sides of the termination criterion selected can be obtained by a call to nag_sparse_complex_herm_basic_diag (f11gt).

The number of operations carried out by nag_sparse_complex_herm_basic_solver (f11gs) for each iteration is likely to be principally determined by the computation of the matrix-vector products $v=Au$ and by the solution of the preconditioning equation $Mv=u$ in the calling program. Each of these operations is carried out once every iteration.
The number of the remaining operations in nag_sparse_complex_herm_basic_solver (f11gs) for each iteration is approximately proportional to $\mathit{n}$. Note that the Lanczos method (SYMMLQ) requires a slightly larger number of operations than the conjugate gradient method.
The number of iterations required to achieve a prescribed accuracy cannot be easily determined at the onset, as it can depend dramatically on the conditioning and spectrum of the preconditioned matrix of the coefficients $\stackrel{-}{A}={E}^{-1}A{E}^{-\mathrm{H}}$.
Additional matrix-vector products are required for the computation of ${‖A‖}_{1}={‖A‖}_{\infty }$, when this has not been supplied to nag_sparse_complex_herm_basic_setup (f11gr) and is required by the termination criterion employed.
The number of operations required to compute ${\sigma }_{1}\left(\stackrel{-}{A}\right)$ is negligible for reasonable values of sigtol and maxits (see Arguments and Further Comments in nag_sparse_complex_herm_basic_setup (f11gr)).
If the termination criterion ${‖{r}_{k}‖}_{p}\le \tau \left({‖b‖}_{p}+{‖A‖}_{p}×{‖{x}_{k}‖}_{p}\right)$ is used (see Description in nag_sparse_complex_herm_basic_setup (f11gr)) and $‖{x}_{0}‖\gg ‖{x}_{k}‖$, so that because of loss of significant digits the required accuracy could not be obtained, the iteration is restarted automatically at some suitable point: nag_sparse_complex_herm_basic_solver (f11gs) sets ${x}_{0}={x}_{k}$ and the computation begins again. For particularly badly scaled problems, more than one restart may be necessary. Naturally, restarting adds to computational costs: it is recommended that the iteration should start from a value ${x}_{0}$ which is as close to the true solution $\stackrel{~}{x}$ as can be estimated. Otherwise, the iteration should start from ${x}_{0}=0$.

Example

See Example in nag_sparse_complex_herm_basic_setup (f11gr).
```function f11gs_example

fprintf('f11gs example results\n\n');

% Solve sparse Hermitian system Ax = b using CG method with
% Incomplete Cholesky preconditioning (IC)

% Define A and b
n  = int64(9);
nz = int64(23);
a    = complex(zeros(3*nz,1));
irow = zeros(3*nz, 1, 'int64');
icol = zeros(3*nz, 1, 'int64');
a(1:nz) = [ 6 + 0i;         -1 + 1i; 6 + 0i;         0 + 1i; 5 + 0i;
5 + 0i;          2 - 2i; 4 + 0i;         1 + 1i; 2 + 0i; 6 + 0i;
-4 + 3i; 0 + 1i; -1 + 0i; 6 + 0i;        -1 - 1i; 0 - 1i; 9 + 0i;
1 + 3i; 1 + 2i; -1 + 0i; 1 + 4i; 9 + 0i];

irow(1:nz) = [1; 2;2; 3;3;  4; 5;5; 6;6;6;  7;7;7;7; 8;8;8;  9;9;9;9;9];
icol(1:nz) = [1; 1;2; 2;3;  4; 1;5; 3;4;6;  2;5;6;7; 4;6;8;  1;5;6;8;9];

b = [ 8 + 54i; -10 - 92i; 25 + 27i;
26 - 28i;  54 + 12i; 26 - 22i;
47 + 65i;  71 - 57i; 60 + 70i];

% Setup IC factorization
lfill  = int64(0);
dtol   = 0;
mic    = 'N';
dscale = 0;
ipiv   = zeros(n, 1, 'int64');

[a, irow, icol, ipiv, istr, nnzc, npivm, ifail] = ...
f11jn( ...
nz, a, irow, icol, lfill, dtol, mic, dscale, ipiv);

% Iterative method setup
method = 'CG    ';
precon = 'Preconditioned';
tol    = (x02aj)^(3/8);
maxitn = int64(20);
anorm  = 0;
sigmax = 0;
maxits = int64(9);
monit  = int64(2);

[lwreq, work, ifail] = ...
f11gr( ...
method, precon, int64(n), tol, maxitn, anorm, sigmax, ...
maxits, monit, 'sigcmp', 's', 'norm_p', '1');

% Reverse communication loop calling f11ge
irevcm = int64(0);
u      = complex(zeros(n,1));
v      = b;
wgt    = zeros(n,1);

while (irevcm ~= 4)
[irevcm, u, v, work, ifail] = ...
f11gs( ...
irevcm, u, v, wgt, work);

if (irevcm == 1)
% v = Au
[v, ifail] = f11xs( ...
a(1:nz), irow(1:nz), icol(1:nz), 'N', u);
elseif (irevcm == 2)
% Solve (IC)v = u
[v, ifail] = f11jp( ...
a, irow, icol, ipiv, istr, 'N', u);
elseif (irevcm == 3)
% Monitoring
[itn, stplhs, stprhs, anorm, sigmax, its, sigerr, ifail] = ...
f11gt(work);
fprintf('\nMonitoring at iteration number %2d\n',itn);
fprintf('residual norm:              %14.4e\n', stplhs);
fprintf('\n   Solution Vector\n');
disp(u);
fprintf('\n   Residual Vector\n');
disp(v);
end
end

% Get information about the computation
[itn, stplhs, stprhs, anorm, sigmax, its, sigerr, ifail] = ...
f11gt(work);

fprintf('\nNumber of iterations for convergence:     %4d\n', itn);
fprintf('Residual norm:                           %14.4e\n', stplhs);
fprintf('Right-hand side of termination criteria: %14.4e\n', stprhs);
fprintf('i-norm of matrix a:                      %14.4e\n', anorm);
fprintf('\n   Solution Vector\n');
disp(u);
fprintf('\n   Residual Vector\n');
disp(v);

```
```f11gs example results

Monitoring at iteration number  2
residual norm:                  1.4937e+01

Solution Vector
0.2142 + 4.5333i
-1.6589 -12.6722i
2.4101 + 7.4551i
4.4400 - 6.4174i
9.1135 + 3.7812i
4.4419 - 4.0382i
1.4757 + 1.2662i
8.4872 - 3.5347i
5.9948 + 0.9685i

Residual Vector
-1.8370 + 3.6956i
-0.6501 + 0.2546i
-0.1262 - 0.1362i
-0.1312 + 0.1413i
-1.1471 + 0.7339i
-0.5505 - 1.0535i
1.7165 - 1.4614i
-0.3583 + 0.2876i
-0.3028 - 0.3532i

Monitoring at iteration number  4
residual norm:                  1.4602e+00

Solution Vector
1.0061 + 8.9847i
1.9637 - 7.9768i
3.0067 + 7.0285i
3.9830 - 5.9636i
5.0390 + 5.0432i
6.0488 - 4.0771i
6.9710 + 3.0168i
8.0118 - 1.9806i
9.0074 + 0.9646i

Residual Vector
0.0115 - 0.0282i
0.0135 - 0.1734i
0.0182 + 0.0196i
0.0189 - 0.0204i
-0.0909 - 0.1090i
-0.2389 + 0.3244i
0.1903 - 0.0155i
0.0516 - 0.0414i
0.0436 + 0.0509i

Number of iterations for convergence:        5
Residual norm:                               9.0594e-14
Right-hand side of termination criteria:     2.8433e-03
i-norm of matrix a:                          2.2000e+01

Solution Vector
1.0000 + 9.0000i
2.0000 - 8.0000i
3.0000 + 7.0000i
4.0000 - 6.0000i
5.0000 + 5.0000i
6.0000 - 4.0000i
7.0000 + 3.0000i
8.0000 - 2.0000i
9.0000 + 1.0000i

Residual Vector
1.0e-13 *

-0.0178 + 0.0000i
0.0355 - 0.2842i
-0.0355 + 0.0355i
0.0355 - 0.0711i
-0.0711 + 0.0355i
-0.0711 + 0.0000i
0.0000 + 0.0000i
0.0000 - 0.0711i
0.0000 - 0.1421i

```