NAG Library Routine Document
F11GEF
1 Purpose
F11GEF is an iterative solver for a symmetric system of simultaneous linear equations; F11GEF is the second in a suite of three routines, where the first routine,
F11GDF, must be called prior to F11GEF to set up the suite, and the third routine in the suite,
F11GFF, can be used to return additional information about the computation.
These three routines are suitable for the solution of large sparse symmetric systems of equations.
2 Specification
INTEGER 
IREVCM, LWORK, IFAIL 
REAL (KIND=nag_wp) 
U(*), V(*), WGT(*), WORK(LWORK) 

3 Description
F11GEF solves the symmetric system of linear simultaneous equations
$Ax=b$ using 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)), a preconditioned Lanczos method based upon the algorithm SYMMLQ (see
Paige and Saunders (1975) and
Barrett et al. (1994)), or the MINRES algorithm (see
Paige and Saunders (1975)).
For a general description of the methods employed you are referred to
Section 3 in F11GDF.
F11GEF can solve the system after the first routine in the suite,
F11GDF, has been called to initialize the computation and specify the method of solution. The third routine in the suite,
F11GFF, can be used to return additional information generated by the computation during monitoring steps and after F11GEF has completed its tasks.
F11GEF uses
reverse communication, i.e., F11GEF returns repeatedly to the calling program with the parameter
IREVCM (see
Section 5) set to specified values which require the calling program to carry out a specific task: either to compute the matrixvector 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 parameter
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.
 Maximum flexibility in the representation and storage of sparse matrices: all matrix operations are performed outside the solver routine, 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.
 Enhanced user interaction: you can closely monitor 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 routines used to perform matrix operations.
4 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 onenorm 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
5 Parameters
Note: this routine uses
reverse communication. Its use involves an initial entry, intermediate exits and reentries, and a final exit, as indicated by the parameter
IREVCM. Between intermediate exits and reentries,
all parameters other than IREVCM and V must remain unchanged.
 1: IREVCM – INTEGERInput/Output
On initial entry: ${\mathbf{IREVCM}}=0$, otherwise an error condition will be raised.
On intermediate reentry: 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. F11GEF will then return with the termination code ${\mathbf{IREVCM}}=4$. Note that before calling F11GEF with ${\mathbf{IREVCM}}=5$ the calling program must have performed the tasks required by the value of IREVCM returned by the previous call to F11GEF, otherwise subsequently returned values may be invalid.
 ${\mathbf{IREVCM}}=6$
 Immediate termination: F11GEF 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. F11GEF will then return with the termination code ${\mathbf{IREVCM}}=4$.
Immediate termination may be useful, for example, when errors are detected during matrixvector multiplication or during the solution of the preconditioning equation.
Changing
IREVCM to any other value between calls will result in an error.
On intermediate exit:
has the following meanings.
 ${\mathbf{IREVCM}}=1$
 The calling program must compute the matrixvector 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 F11GFF can be called at this step.
On final exit: if
${\mathbf{IREVCM}}=4$, F11GEF 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.
Constraint:
on initial entry,
${\mathbf{IREVCM}}=0$; on reentry, either
IREVCM must remain unchanged or be reset to
${\mathbf{IREVCM}}=5$ or
$6$.
 2: U($*$) – REAL (KIND=nag_wp) arrayInput/Output
Note: 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 reentry: must remain unchanged.
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
${{\mathit{i}}}$, the array
U is unchanged from the initial entry to F11GEF. If
${\mathbf{IFAIL}}={\mathbf{1}}$, the array
U is unchanged from the last entry to F11GEF. Otherwise,
U holds the last iterate of the solution of the system of equations, for all returned values of
IFAIL.
 3: V($*$) – REAL (KIND=nag_wp) arrayInput/Output

Note: the dimension of the array
V
must be at least
$\mathit{n}$.
On initial entry: the righthand side $b$ of the system of equations $Ax=b$.
On intermediate reentry: 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 F11GEF.
If
${\mathbf{IREVCM}}=3$,
V must remain unchanged.
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
${{\mathit{i}}}$, the array
V is unchanged from the last entry to F11GEF. If
${\mathbf{IFAIL}}={\mathbf{1}}$, the array
V is unchanged from the initial entry to F11GEF. If
${\mathbf{IFAIL}}={\mathbf{0}}$ or
${\mathbf{2}}$, the array
V contains the true residual vector of the system of equations (see also
Section 6). 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: WGT($*$) – REAL (KIND=nag_wp) arrayInput

Note: the dimension of the array
WGT
must be at least
$\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,\mathit{n}\right)$.
On entry: the usersupplied weights, if these are to be used in the computation of the vector norms in the termination criterion (see
Sections 3 and
5 in F11GDF).
Weights are NOT used in the MINRES algorithm.
Constraint:
if weights are to be used, at least one element of
WGT must be nonzero.
 5: WORK(LWORK) – REAL (KIND=nag_wp) arrayCommunication Array
On initial entry: the array
WORK as returned by
F11GDF (see also
Section 5 in F11GDF).
On intermediate reentry: must remain unchanged.
 6: LWORK – INTEGERInput
On initial entry: the dimension of the array
WORK as declared in the (sub)program from which F11GEF is called (see also
Section 3 in F11GDF).
The required amount of workspace is as follows:
Method 
Requirements 
CG 
${\mathbf{LWORK}}=120+5\mathit{n}+p$. 
SYMMLQ 
${\mathbf{LWORK}}=120+6\mathit{n}+p$, 
MINRES 
${\mathbf{LWORK}}=120+9\mathit{n}$, 
where
 $p=2*\left({\mathbf{MAXITS}}+1\right)$, when an estimate of ${\sigma}_{1}\left(A\right)$ (SIGMAX) is computed;
 $p=0$, otherwise.
Constraint:
${\mathbf{LWORK}}\ge {\mathbf{LWREQ}}$, where
LWREQ is returned by
F11GDF.
 7: IFAIL – INTEGERInput/Output
On initial entry:
IFAIL must be set to
$0$,
$1\text{ or}1$. If you are unfamiliar with this parameter you should refer to
Section 3.3 in the Essential Introduction for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value
$1\text{ or}1$ is recommended. If the output of error messages is undesirable, then the value
$1$ is recommended. Otherwise, because for this routine the values of the output parameters may be useful even if
${\mathbf{IFAIL}}\ne {\mathbf{0}}$ on exit, the recommended value is
$1$.
When the value $\mathbf{1}\text{ or}1$ is used it is essential to test the value of IFAIL on exit.
On final exit:
${\mathbf{IFAIL}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see
Section 6).
6 Error Indicators and Warnings
If on entry
${\mathbf{IFAIL}}={\mathbf{0}}$ or
${{\mathbf{1}}}$, explanatory error messages are output on the current error message unit (as defined by
X04AAF).
Errors or warnings detected by the routine:
 ${\mathbf{IFAIL}}=i$
On entry, the $i$th argument had an illegal value.
 ${\mathbf{IFAIL}}=1$
F11GEF 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
F11GFF have remained unchanged.
 ${\mathbf{IFAIL}}=2$
The required accuracy could not be obtained. However, F11GEF has terminated with reasonable accuracy: the last iterate of the residual satisfied the termination criterion but the exact residual
$r=bAx$, 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 satisfactory solved to within or close to the accuracy available on your system. Further iterations are unlikely to improve on this situation. You should call
F11GFF to check the values of the leftand righthand side of the termination condition.
 ${\mathbf{IFAIL}}=3$
F11GDF was either not called before calling F11GEF or it returned an error. The arrays
U and
V remain unchanged.
 ${\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.
 ${\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: all methods require a positive definite preconditioner (see also
Section 3). 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}}=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.
 ${\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$
The weights in array
WGT are all equal to zero, or at least one of them is negative.
7 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}=bA{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 userspecified tolerance, as described in
Section 3 in F11GDF. The computed values of the left and righthand sides of the termination criterion selected can be obtained by a call to
F11GFF.
The number of operations carried out by F11GEF for each iteration is likely to be principally determined by the computation of the matrixvector 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 F11GEF 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{T}}$.
Additional matrixvector products are required for the computation of
${\Vert A\Vert}_{1}={\Vert A\Vert}_{\infty}$, when this has not been supplied to
F11GDF 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
Sections 5 and
8 in F11GDF).
If the termination criterion
${\Vert {r}_{k}\Vert}_{p}\le \tau \left({\Vert b\Vert}_{p}+{\Vert A\Vert}_{p}\times {\Vert {x}_{k}\Vert}_{p}\right)$ is used (see
Section 3 in F11GDF) and
$\Vert {x}_{0}\Vert \gg \Vert {x}_{k}\Vert $, so that because of loss of significant digits the required accuracy could not be obtained, the iteration is restarted automatically at some suitable point: F11GEF 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$.
9 Example