NAG Library Routine Document
F11GRF
1 Purpose
F11GRF is a setup routine, the first in a suite of three routines for the iterative solution of a complex Hermitian system of simultaneous linear equations. F11GRF must be called before
F11GSF, the iterative solver. The third routine in the suite,
F11GTF, can be used to return additional information about the computation.
These three routines are suitable for the solution of large sparse complex Hermitian systems of equations.
2 Specification
SUBROUTINE F11GRF ( 
METHOD, PRECON, SIGCMP, NORM, WEIGHT, ITERM, N, TOL, MAXITN, ANORM, SIGMAX, SIGTOL, MAXITS, MONIT, LWREQ, WORK, LWORK, IFAIL) 
INTEGER 
ITERM, N, MAXITN, MAXITS, MONIT, LWREQ, LWORK, IFAIL 
REAL (KIND=nag_wp) 
TOL, ANORM, SIGMAX, SIGTOL 
COMPLEX (KIND=nag_wp) 
WORK(LWORK) 
CHARACTER(*) 
METHOD 
CHARACTER(1) 
PRECON, SIGCMP, NORM, WEIGHT 

3 Description
The suite consisting of the
routines F11GRF,
F11GSF and
F11GTF
is designed to solve the complex Hermitian system of simultaneous linear equations
$Ax=b$ of order
$n$, where
$n$ is large and the matrix of the coefficients
$A$ is sparse.
F11GRF is a setup routine which must be called before the iterative solver
F11GSF.
F11GTF, the third routine in the suite, can be used to return additional information about the computation. Either of two methods can be used:
Both CG and SYMMLQ methods start from the residual
${r}_{0}=bA{x}_{0}$, where
${x}_{0}$ is an initial estimate for the solution (often
${x}_{0}=0$), and generate an orthogonal basis for the Krylov subspace
$\mathrm{span}\left\{{A}^{\mathit{k}}{r}_{0}\right\}$, for
$\mathit{k}=0,1,\dots $, by means of threeterm recurrence relations (see
Golub and Van Loan (1996)). A sequence of real symmetric tridiagonal matrices
$\left\{{T}_{k}\right\}$ is also generated. Here and in the following, the index
$k$ denotes the iteration count. The resulting real symmetric tridiagonal systems of equations are usually more easily solved than the original problem. A sequence of solution iterates
$\left\{{x}_{k}\right\}$ is thus generated such that the sequence of the norms of the residuals
$\left\{\Vert {r}_{k}\Vert \right\}$ converges to a required tolerance. Note that, in general, the convergence is not monotonic.
In exact arithmetic, after $n$ iterations, this process is equivalent to an orthogonal reduction of $A$ to real symmetric tridiagonal form, ${T}_{n}={Q}^{\mathrm{H}}AQ$; the solution ${x}_{n}$ would thus achieve exact convergence. In finiteprecision arithmetic, cancellation and roundoff errors accumulate causing loss of orthogonality. These methods must therefore be viewed as genuinely iterative methods, able to converge to a solution within a prescribed tolerance.
The orthogonal basis is not formed explicitly in either method. The basic difference between the two methods lies in the method of solution of the resulting real symmetric tridiagonal systems of equations: the conjugate gradient method is equivalent to carrying out an $LD{L}^{\mathrm{H}}$ (Cholesky) factorization whereas the Lanczos method (SYMMLQ) uses an $LQ$ factorization.
Faster convergence can be achieved using a
preconditioner (see
Golub and Van Loan (1996) and
Barrett et al. (1994)). A preconditioner maps the original system of equations onto a different system, say
with, hopefully, better characteristics with respect to its speed of convergence: for example, the condition number of the matrix of the coefficients can be improved or eigenvalues in its spectrum can be made to coalesce. An orthogonal basis for the Krylov subspace
$\mathrm{span}\left\{{\stackrel{}{A}}^{\mathit{k}}{\stackrel{}{r}}_{0}\right\}$, for
$\mathit{k}=0,1,\dots $, is generated and the solution proceeds as outlined above. The algorithms used are such that the solution and residual iterates of the original system are produced, not their preconditioned counterparts. Note that an unsuitable preconditioner or no preconditioning at all may result in a very slow rate, or lack, of convergence. However, preconditioning involves a tradeoff between the reduction in the number of iterations required for convergence and the additional computational costs per iteration. Also, setting up a preconditioner may involve nonnegligible overheads.
A preconditioner must be
Hermitian and positive definite, i.e., representable by
$M=E{E}^{\mathrm{H}}$, where
$M$ is nonsingular, and such that
$\stackrel{}{A}={E}^{1}A{E}^{\mathrm{H}}\sim {I}_{n}$ in
(1), where
${I}_{n}$ is the identity matrix of order
$n$. Also, we can define
$\stackrel{}{r}={E}^{1}r$ and
$\stackrel{}{x}={E}^{\mathrm{H}}x$. These are formal definitions, used only in the design of the algorithms; in practice, only the means to compute the matrixvector products
$v=Au$ and to solve the preconditioning equations
$Mv=u$ are required, that is, explicit information about
$M$,
$E$ or their inverses is not required at any stage.
The first termination criterion
is available for both conjugate gradient and Lanczos (SYMMLQ) methods. In
(2),
$p=1,\infty \text{ or}2$ and
$\tau $ denotes a userspecified tolerance subject to
$\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(10,\sqrt{n}\right)\epsilon \le \tau <1$, where
$\epsilon $ is the
machine precision. Facilities are provided for the estimation of the norm of the matrix of the coefficients
${\Vert A\Vert}_{1}={\Vert A\Vert}_{\infty}$, when this is not known in advance, used in
(2), by applying Higham's method (see
Higham (1988)). Note that
${\Vert A\Vert}_{2}$ cannot be estimated internally. This criterion uses an error bound derived from
backward error analysis to ensure that the computed solution is the exact solution of a problem as close to the original as the termination tolerance requires. Termination criteria employing bounds derived from
forward error analysis could be used, but any such criteria would require information about the condition number
$\kappa \left(A\right)$ which is not easily obtainable.
The second termination criterion
is available only for the Lanczos method (SYMMLQ). In
(3),
${\sigma}_{1}\left(\stackrel{}{A}\right)={\Vert \stackrel{}{A}\Vert}_{2}$ is the largest singular value of the (preconditioned) iteration matrix
$\stackrel{}{A}$. This termination criterion monitors the progress of the solution of the preconditioned system of equations and is less expensive to apply than criterion
(2). When
${\sigma}_{1}\left(\stackrel{}{A}\right)$ is not supplied, facilities are provided for its estimation by
${\sigma}_{1}\left(\stackrel{}{A}\right)\sim {\displaystyle \underset{k}{\mathrm{max}}}\phantom{\rule{0.25em}{0ex}}{\sigma}_{1}\left({T}_{k}\right)$. The interlacing property
${\sigma}_{1}\left({T}_{k1}\right)\le {\sigma}_{1}\left({T}_{k}\right)$ and Gerschgorin's theorem provide lower and upper bounds from which
${\sigma}_{1}\left({T}_{k}\right)$ can be easily computed by bisection. Alternatively, the less expensive estimate
${\sigma}_{1}\left(\stackrel{}{A}\right)\sim {\displaystyle \underset{k}{\mathrm{max}}}\phantom{\rule{0.25em}{0ex}}{\Vert {T}_{k}\Vert}_{1}$ can be used, where
${\sigma}_{1}\left(\stackrel{}{A}\right)\le {\Vert {T}_{k}\Vert}_{1}$ by Gerschgorin's theorem. Note that only order of magnitude estimates are required by the termination criterion.
Termination criterion
(2) is the recommended choice, despite its (small) additional costs per iteration when using the Lanczos method (SYMMLQ). Also, if the norm of the initial estimate is much larger than the norm of the solution, that is, if
$\Vert {x}_{0}\Vert \gg \Vert x\Vert $, a dramatic loss of significant digits could result in complete lack of convergence. The use of criterion
(2) will enable the detection of such a situation, and the iteration will be restarted at a suitable point. No such restart facilities are provided for criterion
(3).
Optionally, a vector
$w$ of userspecified weights can be used in the computation of the vector norms in termination criterion
(2), i.e.,
${{\Vert v\Vert}_{p}}^{\left(w\right)}={\Vert {v}^{\left(w\right)}\Vert}_{p}$, where
${\left({v}^{\left(w\right)}\right)}_{\mathit{i}}={w}_{\mathit{i}}{v}_{\mathit{i}}$, for
$\mathit{i}=1,2,\dots ,n$. Note that the use of weights increases the computational costs.
The sequence of calls to the routines comprising the suite is enforced: first, the setup routine F11GRF must be called, followed by the solver
F11GSF.
F11GTF can be called either when
F11GSF is carrying out a monitoring step or after
F11GSF has completed its tasks. Incorrect sequencing will raise an error condition.
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
 1: $\mathrm{METHOD}$ – CHARACTER(*)Input

On entry: the iterative method to be used.
 ${\mathbf{METHOD}}=\text{'CG'}$
 Conjugate gradient method.
 ${\mathbf{METHOD}}=\text{'SYMMLQ'}$
 Lanczos method (SYMMLQ).
Constraint:
${\mathbf{METHOD}}=\text{'CG'}$ or $\text{'SYMMLQ'}$.
 2: $\mathrm{PRECON}$ – CHARACTER(1)Input

On entry: determines whether preconditioning is used.
 ${\mathbf{PRECON}}=\text{'N'}$
 No preconditioning.
 ${\mathbf{PRECON}}=\text{'P'}$
 Preconditioning.
Constraint:
${\mathbf{PRECON}}=\text{'N'}$ or $\text{'P'}$.
 3: $\mathrm{SIGCMP}$ – CHARACTER(1)Input

On entry: determines whether an estimate of
${\sigma}_{1}\left(\stackrel{}{A}\right)={\Vert {E}^{1}A{E}^{\mathrm{H}}\Vert}_{2}$, the largest singular value of the preconditioned matrix of the coefficients, is to be computed using the bisection method on the sequence of tridiagonal matrices
$\left\{{T}_{k}\right\}$ generated during the iteration. Note that
$\stackrel{}{A}=A$ when a preconditioner is not used.
If
${\mathbf{SIGMAX}}>0.0$ (see below), i.e., when
${\sigma}_{1}\left(\stackrel{}{A}\right)$ is supplied, the value of
SIGCMP is ignored.
 ${\mathbf{SIGCMP}}=\text{'S'}$
 ${\sigma}_{1}\left(\stackrel{}{A}\right)$ is to be computed using the bisection method.
 ${\mathbf{SIGCMP}}=\text{'N'}$
 The bisection method is not used.
If the termination criterion
(3) is used, requiring
${\sigma}_{1}\left(\stackrel{}{A}\right)$, an inexpensive estimate is computed and used (see
Section 3).
Suggested value:
${\mathbf{SIGCMP}}=\text{'N'}$.
Constraint:
${\mathbf{SIGCMP}}=\text{'S'}$ or $\text{'N'}$.
 4: $\mathrm{NORM}$ – CHARACTER(1)Input

On entry: defines the matrix and vector norm to be used in the termination criteria.
 ${\mathbf{NORM}}=\text{'1'}$
 Use the ${l}_{1}$ norm.
 ${\mathbf{NORM}}=\text{'I'}$
 Use the ${l}_{\infty}$ norm.
 ${\mathbf{NORM}}=\text{'2'}$
 Use the ${l}_{2}$ norm.
Suggested values:
 if ${\mathbf{ITERM}}=1$, ${\mathbf{NORM}}=\text{'I'}$;
 if ${\mathbf{ITERM}}=2$, ${\mathbf{NORM}}=\text{'2'}$.
Constraints:
 if ${\mathbf{ITERM}}=1$, ${\mathbf{NORM}}=\text{'1'}$, $\text{'I'}$ or $\text{'2'}$;
 if ${\mathbf{ITERM}}=2$, ${\mathbf{NORM}}=\text{'2'}$.
 5: $\mathrm{WEIGHT}$ – CHARACTER(1)Input

On entry: specifies whether a vector
$w$ of usersupplied weights is to be used in the vector norms used in the computation of termination criterion
(2) (
${\mathbf{ITERM}}=1$):
${{\Vert v\Vert}_{p}}^{\left(w\right)}={\Vert {v}^{\left(w\right)}\Vert}_{p}$, where
${v}_{\mathit{i}}^{\left(w\right)}={w}_{\mathit{i}}{v}_{\mathit{i}}$, for
$\mathit{i}=1,2,\dots ,n$. The suffix
$p=1,2,\infty $ denotes the vector norm used, as specified by the parameter
NORM. Note that weights cannot be used when
${\mathbf{ITERM}}=2$, i.e., when criterion
(3) is used.
 ${\mathbf{WEIGHT}}=\text{'W'}$
 Usersupplied weights are to be used and must be supplied on initial entry to F11GSF.
 ${\mathbf{WEIGHT}}=\text{'N'}$
 All weights are implicitly set equal to one. Weights do not need to be supplied on initial entry to F11GSF.
Suggested value:
${\mathbf{WEIGHT}}=\text{'N'}$.
Constraints:
 if ${\mathbf{ITERM}}=1$, ${\mathbf{WEIGHT}}=\text{'W'}$ or $\text{'N'}$;
 if ${\mathbf{ITERM}}=2$, ${\mathbf{WEIGHT}}=\text{'N'}$.
 6: $\mathrm{ITERM}$ – INTEGERInput

On entry: defines the termination criterion to be used.
 ${\mathbf{ITERM}}=1$
 Use the termination criterion defined in (2) (both conjugate gradient and Lanczos (SYMMLQ) methods).
 ${\mathbf{ITERM}}=2$
 Use the termination criterion defined in (3) (Lanczos method (SYMMLQ) only).
Suggested value:
${\mathbf{ITERM}}=1$.
Constraints:
 if ${\mathbf{METHOD}}=\text{'CG'}$, ${\mathbf{ITERM}}=1$;
 if ${\mathbf{METHOD}}=\text{'SYMMLQ'}$, ${\mathbf{ITERM}}=1$ or $2$.
 7: $\mathrm{N}$ – INTEGERInput

On entry: $n$, the order of the matrix $A$.
Constraint:
${\mathbf{N}}>0$.
 8: $\mathrm{TOL}$ – REAL (KIND=nag_wp)Input

On entry: the tolerance
$\tau $ for the termination criterion.
If ${\mathbf{TOL}}\le 0.0$, $\tau =\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(\sqrt{\epsilon},\sqrt{n}\epsilon \right)$ is used, where $\epsilon $ is the machine precision.
Otherwise $\tau =\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{TOL}},10\epsilon ,\sqrt{n}\epsilon \right)$ is used.
Constraint:
${\mathbf{TOL}}<1.0$.
 9: $\mathrm{MAXITN}$ – INTEGERInput

On entry: the maximum number of iterations.
Constraint:
${\mathbf{MAXITN}}>0$.
 10: $\mathrm{ANORM}$ – REAL (KIND=nag_wp)Input

On entry: if
${\mathbf{ANORM}}>0.0$, the value of
${\Vert A\Vert}_{p}$ to be used in the termination criterion
(2) (
${\mathbf{ITERM}}=1$).
If
${\mathbf{ANORM}}\le 0.0$,
${\mathbf{ITERM}}=1$ and
${\mathbf{NORM}}=\text{'1'}$ or
$\text{'I'}$, then
${\Vert A\Vert}_{1}={\Vert A\Vert}_{\infty}$ is estimated internally by
F11GSF.
If
${\mathbf{ITERM}}=2$, then
ANORM is not referenced.
Constraint:
if ${\mathbf{ITERM}}=1$ and ${\mathbf{NORM}}=2$, ${\mathbf{ANORM}}>0.0$.
 11: $\mathrm{SIGMAX}$ – REAL (KIND=nag_wp)Input

On entry: if
${\mathbf{SIGMAX}}>0.0$, the value of
${\sigma}_{1}\left(\stackrel{}{A}\right)={\Vert {E}^{1}A{E}^{\mathrm{H}}\Vert}_{2}$.
If
${\mathbf{SIGMAX}}\le 0.0$,
${\sigma}_{1}\left(\stackrel{}{A}\right)$ is estimated by
F11GSF when either
${\mathbf{SIGCMP}}=\text{'S'}$ or termination criterion
(3) (
${\mathbf{ITERM}}=2$) is employed, though it will be used only in the latter case.
Otherwise,
SIGMAX is not referenced.
 12: $\mathrm{SIGTOL}$ – REAL (KIND=nag_wp)Input

On entry: the tolerance used in assessing the convergence of the estimate of
${\sigma}_{1}\left(\stackrel{}{A}\right)={\Vert \stackrel{}{A}\Vert}_{2}$ when the bisection method is used.
If ${\mathbf{SIGTOL}}\le 0.0$, the default value ${\mathbf{SIGTOL}}=0.01$ is used. The actual value used is $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{SIGTOL}},\epsilon \right)$.
If
${\mathbf{SIGCMP}}=\text{'N'}$ or
${\mathbf{SIGMAX}}>0.0$, then
SIGTOL is not referenced.
Suggested value:
${\mathbf{SIGTOL}}=0.01$ should be sufficient in most cases.
Constraint:
if ${\mathbf{SIGCMP}}=\text{'S'}$ and ${\mathbf{SIGMAX}}\le 0.0$, ${\mathbf{SIGTOL}}<1.0$.
 13: $\mathrm{MAXITS}$ – INTEGERInput

On entry: the maximum iteration number
$k={\mathbf{MAXITS}}$ for which
${\sigma}_{1}\left({T}_{k}\right)$ is computed by bisection (see also
Section 3). If
${\mathbf{SIGCMP}}=\text{'N'}$ or
${\mathbf{SIGMAX}}>0.0$, then
MAXITS is not referenced.
Suggested value:
${\mathbf{MAXITS}}=\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left(10,n\right)$ when
SIGTOL is of the order of its default value
$\left(0.01\right)$.
Constraint:
if ${\mathbf{SIGCMP}}=\text{'S'}$ and ${\mathbf{SIGMAX}}\le 0.0$, $1\le {\mathbf{MAXITS}}\le {\mathbf{MAXITN}}$.
 14: $\mathrm{MONIT}$ – INTEGERInput

On entry: if
${\mathbf{MONIT}}>0$, the frequency at which a monitoring step is executed by
F11GSF: the current solution and residual iterates will be returned by
F11GSF and a call to
F11GTF made possible every
MONIT iterations, starting from iteration number
MONIT. Otherwise, no monitoring takes place. There are some additional computational costs involved in monitoring the solution and residual vectors when the Lanczos method (SYMMLQ) is used.
Constraint:
${\mathbf{MONIT}}\le {\mathbf{MAXITN}}$.
 15: $\mathrm{LWREQ}$ – INTEGEROutput

On exit: the minimum amount of workspace required by
F11GSF. (See also
Section 5 in F11GSF.)
 16: $\mathrm{WORK}\left({\mathbf{LWORK}}\right)$ – COMPLEX (KIND=nag_wp) arrayCommunication Array

On exit: the array
WORK is initialized by F11GRF. It must
not be modified before calling the next routine in the suite, namely
F11GSF.
 17: $\mathrm{LWORK}$ – INTEGERInput

On entry: the dimension of the array
WORK as declared in the (sub)program from which F11GRF is called.
Constraint:
${\mathbf{LWORK}}\ge 120$.
Note: although the minimum value of
LWORK ensures the correct functioning of F11GRF, a larger value is required by the other routines in the suite, namely
F11GSF and
F11GTF. The required value is as follows:
Method 
Requirements 
CG 
${\mathbf{LWORK}}=120+5n+p$ 
SYMMLQ 
${\mathbf{LWORK}}=120+6n+p$ 
where
 $p=2\times \left({\mathbf{MAXITS}}+1\right)$, when an estimate of ${\sigma}_{1}\left(A\right)$ (SIGMAX) is computed;
 $p=0$, otherwise.
 18: $\mathrm{IFAIL}$ – INTEGERInput/Output

On 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, if you are not familiar with this parameter, the recommended value is
$0$.
When the value $\mathbf{1}\text{ or}\mathbf{1}$ is used it is essential to test the value of IFAIL on exit.
On 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$

F11GRF has been called out of sequence.
 ${\mathbf{IFAIL}}=99$
An unexpected error has been triggered by this routine. Please
contact
NAG.
See
Section 3.8 in the Essential Introduction for further information.
 ${\mathbf{IFAIL}}=399$
Your licence key may have expired or may not have been installed correctly.
See
Section 3.7 in the Essential Introduction for further information.
 ${\mathbf{IFAIL}}=999$
Dynamic memory allocation failed.
See
Section 3.6 in the Essential Introduction for further information.
7 Accuracy
Not applicable.
8 Parallelism and Performance
Not applicable.
When
${\sigma}_{1}\left(\stackrel{}{A}\right)$ is not supplied (
${\mathbf{SIGMAX}}\le 0.0$) but it is required, it is estimated by
F11GSF using either of the two methods described in
Section 3, as specified by the parameter
SIGCMP. In particular, if
${\mathbf{SIGCMP}}=\text{'S'}$, then the computation of
${\sigma}_{1}\left(\stackrel{}{A}\right)$ is deemed to have converged when the differences between three successive values of
${\sigma}_{1}\left({T}_{k}\right)$ differ, in a relative sense, by less than the tolerance
SIGTOL, i.e., when
The computation of
${\sigma}_{1}\left(\stackrel{}{A}\right)$ is also terminated when the iteration count exceeds the maximum value allowed, i.e.,
$k\ge {\mathbf{MAXITS}}$.
Bisection is increasingly expensive with increasing iteration count. A reasonably large value of
SIGTOL, of the order of the suggested value, is recommended and an excessive value of
MAXITS should be avoided. Under these conditions,
${\sigma}_{1}\left(\stackrel{}{A}\right)$ usually converges within very few iterations.
10 Example
This example solves a complex Hermitian system of simultaneous linear equations using the conjugate gradient method, where the matrix of the coefficients
$A$, has a random sparsity pattern. An incomplete Cholesky preconditioner is used (
F11JAF and
F11JBF).
10.1 Program Text
Program Text (f11grfe.f90)
10.2 Program Data
Program Data (f11grfe.d)
10.3 Program Results
Program Results (f11grfe.r)