F11GDF (PDF version)
F11 Chapter Contents
F11 Chapter Introduction
NAG Library Manual

NAG Library Routine Document

F11GDF

Note:  before using this routine, please read the Users' Note for your implementation to check the interpretation of bold italicised terms and other implementation-dependent details.

+ Contents

    1  Purpose
    7  Accuracy

1  Purpose

F11GDF is a setup routine, the first in a suite of three routines for the iterative solution of a symmetric system of simultaneous linear equations. F11GDF must be called before the iterative solver, F11GEF. 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  ITERM, N, MAXITN, MAXITS, MONIT, LWREQ, LWORK, IFAIL
REAL (KIND=nag_wp)  TOL, ANORM, SIGMAX, SIGTOL, WORK(LWORK)
CHARACTER(*)  METHOD
CHARACTER(1)  PRECON, SIGCMP, NORM, WEIGHT

3  Description

The suite consisting of the routines F11GDF, F11GEF and F11GFF is designed to solve the symmetric system of simultaneous linear equations Ax=b of order n, where n is large and the matrix of the coefficients A is sparse.
F11GDF is a setup routine which must be called before F11GEF, the iterative solver. The third routine in the suite, F11GFF can be used to return additional information about the computation. One of the following methods can be used:
  1. Conjugate Gradient Method (CG)
    For this method (see Hestenes and Stiefel (1952), Golub and Van Loan (1996), Barrett et al. (1994) and Dias da Cunha and Hopkins (1994)), the matrix A should ideally be positive definite. The application of the Conjugate Gradient method to indefinite matrices may lead to failure or to lack of convergence.
  2. Lanczos Method (SYMMLQ)
    This method, based upon the algorithm SYMMLQ (see Paige and Saunders (1975) and Barrett et al. (1994)), is suitable for both positive definite and indefinite matrices. It is more robust than the Conjugate Gradient method but less efficient when A is positive definite.
  3. Minimum Residual Method (MINRES)
    This method may be used when the matrix is indefinite. It seeks to reduce the norm of the residual at each iteration and often takes fewer iterations than the other methods. It does however require slightly more memory.
The CG and SYMMLQ methods start from the residual r0=b-Ax0, where x0 is an initial estimate for the solution (often x0=0), and generate an orthogonal basis for the Krylov subspace spanAkr0, for k=0,1,, by means of three-term recurrence relations (see Golub and Van Loan (1996)). A sequence of symmetric tridiagonal matrices Tk is also generated. Here and in the following, the index k denotes the iteration count. The resulting symmetric tridiagonal systems of equations are usually more easily solved than the original problem. A sequence of solution iterates xk is thus generated such that the sequence of the norms of the residuals rk 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 symmetric tridiagonal form, Tn=QTAQ; the solution xn would thus achieve exact convergence. In finite-precision arithmetic, cancellation and round-off 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 Conjugate Gradient and Lanczos methods lies in the method of solution of the resulting symmetric tridiagonal systems of equations: the conjugate gradient method is equivalent to carrying out an LDLT (Cholesky) factorization whereas the Lanczos method (SYMMLQ) uses an LQ factorization.
Faster convergence for all the methods 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
A-x-=b-, (1)
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 spanA-kr-0, for k=0,1,, 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 trade-off 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 non-negligible overheads.
A preconditioner must be symmetric and positive definite, i.e., representable by M=EET, where M is nonsingular, and such that A-=E-1AE-TIn in (1), where In is the identity matrix of order n. Also, we can define r-=E-1r and x-=ETx. These are formal definitions, used only in the design of the algorithms; in practice, only the means to compute the matrix-vector 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
rkp τ bp + Ap × xkp (2)
is available for both conjugate gradient and Lanczos (SYMMLQ) methods. In (2), p=1,​ or ​2 and τ denotes a user-specified tolerance subject to max10,nετ<1, where ε is the machine precision. Facilities are provided for the estimation of the norm of the matrix of the coefficients A1=A, when this is not known in advance, used in (2), by applying Higham's method (see Higham (1988)). Note that A2 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 κA which is not easily obtainable.
The second termination criterion
r-k2 τ max1.0, b2 / r02 r-0 2 + σ1 A- × Δx-k2 (3)
is available only for the Lanczos method (SYMMLQ). In (3), σ1A-=A-2 is the largest singular value of the (preconditioned) iteration matrix 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 σ1A- is not supplied, facilities are provided for its estimation by σ1A-maxkσ1Tk. The interlacing property σ1Tk-1σ1Tk and Gerschgorin's theorem provide lower and upper bounds from which σ1Tk can be easily computed by bisection. Alternatively, the less expensive estimate σ1A-maxkTk1 can be used, where σ1A-Tk1 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 x0x, 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 user-specified weights can be used in the computation of the vector norms in termination criterion (2), i.e., vpw=v w p, where v w i=wi vi, for i=1,2,,n. Note that the use of weights increases the computational costs.
The MINRES algorithm terminates when the norm of the residual of the preconditioned system F, F2τ× A-2× xk2 , where A- is the preconditioned matrix.
The sequence of calls to the routines comprising the suite is enforced: first, the setup routine F11GDF must be called, followed by the solver F11GEF. The diagnostic routine F11GFF can be called either when F11GEF is carrying out a monitoring step or after F11GEF 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 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

5  Parameters

1:     METHOD – CHARACTER(*)Input
On entry: the iterative method to be used.
METHOD='CG'
Conjugate gradient method (CG).
METHOD='SYMMLQ'
Lanczos method (SYMMLQ).
METHOD='MINRES'
Minimum residual method (MINRES).
Constraint: METHOD='CG', 'SYMMLQ' or 'MINRES'.
2:     PRECON – CHARACTER(1)Input
On entry: determines whether preconditioning is used.
PRECON='N'
No preconditioning.
PRECON='P'
Preconditioning.
Constraint: PRECON='N' or 'P'.
3:     SIGCMP – CHARACTER(1)Input
On entry: determines whether an estimate of σ1A-=E-1AE-T2, 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 Tk generated during the iteration. Note that A-=A when a preconditioner is not used.
If SIGMAX>0.0 (see below), i.e., when σ1A- is supplied, the value of SIGCMP is ignored.
SIGCMP='S'
σ1A- is to be computed using the bisection method.
SIGCMP='N'
The bisection method is not used.
If the termination criterion (3) is used, requiring σ1A-, an inexpensive estimate is computed and used (see Section 3).
It is not used if METHOD='MINRES'.
Suggested value: SIGCMP='N'.
Constraint: SIGCMP='S' or 'N'.
4:     NORM – CHARACTER(1)Input
On entry: if METHOD='CG' or 'SYMMLQ', NORM defines the matrix and vector norm to be used in the termination criteria.
NORM='1'
Use the l1 norm.
NORM='I'
Use the l norm.
NORM='2'
Use the l2 norm.
It has no effect if METHOD='MINRES'.
Suggested values:
  • if ITERM=1, NORM='I';
  • if ITERM=2, NORM='2'.
Constraints:
  • if ITERM=1, NORM='1', 'I' or '2';
  • if ITERM=2, NORM='2'.
5:     WEIGHT – CHARACTER(1)Input
On entry: specifies whether a vector w of user-supplied weights is to be used in the vector norms used in the computation of termination criterion (2) (ITERM=1): vpw=v w p, where vi w =wi vi, for i=1,2,,n. The suffix p=1,2, denotes the vector norm used, as specified by the parameter NORM. Note that weights cannot be used when ITERM=2, i.e., when criterion (3) is used.
WEIGHT='W'
User-supplied weights are to be used and must be supplied on initial entry to F11GEF.
WEIGHT='N'
All weights are implicitly set equal to one. Weights do not need to be supplied on initial entry to F11GEF.
It has no effect if METHOD='MINRES'.
Suggested value: WEIGHT='N'.
Constraints:
  • if ITERM=1, WEIGHT='W' or 'N';
  • if ITERM=2, WEIGHT='N'.
6:     ITERM – INTEGERInput
On entry: defines the termination criterion to be used.
ITERM=1
Use the termination criterion defined in (2) (both conjugate gradient and Lanczos (SYMMLQ) methods).
ITERM=2
Use the termination criterion defined in (3) (Lanczos method (SYMMLQ) only).
It has no effect if METHOD='MINRES'.
Suggested value: ITERM=1.
Constraints:
  • if METHOD='CG', ITERM=1;
  • if METHOD='SYMMLQ', ITERM=1 or 2.
7:     N – INTEGERInput
On entry: n, the order of the matrix A.
Constraint: N>0.
8:     TOL – REAL (KIND=nag_wp)Input
On entry: the tolerance τ for the termination criterion.
If TOL0.0, τ=maxε,nε is used, where ε is the machine precision.
Otherwise τ=maxTOL,10ε,nε is used.
Constraint: TOL<1.0.
9:     MAXITN – INTEGERInput
On entry: the maximum number of iterations.
Constraint: MAXITN>0.
10:   ANORM – REAL (KIND=nag_wp)Input
On entry: if ANORM>0.0, the value of Ap to be used in the termination criterion (2) (ITERM=1).
If ANORM0.0, ITERM=1 and NORM='1' or 'I', then A1=A is estimated internally by F11GEF.
If ITERM=2, then ANORM is not referenced.
It has no effect if METHOD='MINRES'.
Constraint: if ITERM=1 and NORM=2, ANORM>0.0.
11:   SIGMAX – REAL (KIND=nag_wp)Input
On entry: if SIGMAX>0.0, the value of σ1A-=E-1AE-T2.
If SIGMAX0.0, σ1A- is estimated by F11GEF when either SIGCMP='S' or termination criterion (3) (ITERM=2) is employed, though it will be used only in the latter case.
Otherwise, or if METHOD='MINRES', SIGMAX is not referenced.
12:   SIGTOL – REAL (KIND=nag_wp)Input
On entry: the tolerance used in assessing the convergence of the estimate of σ1A-=A-2 when the bisection method is used.
If SIGTOL0.0, the default value SIGTOL=0.01 is used. The actual value used is maxSIGTOL,ε.
If SIGCMP='N' or SIGMAX>0.0, then SIGTOL is not referenced.
It has no effect if METHOD='MINRES'.
Suggested value: SIGTOL=0.01 should be sufficient in most cases.
Constraint: if SIGCMP='S' and SIGMAX0.0, SIGTOL<1.0.
13:   MAXITS – INTEGERInput
On entry: the maximum iteration number k=MAXITS for which σ1Tk is computed by bisection (see also Section 3). If SIGCMP='N' or SIGMAX>0.0, or if METHOD='MINRES', then MAXITS is not referenced.
Suggested value: MAXITS=min10,n when SIGTOL is of the order of its default value 0.01.
Constraint: if SIGCMP='S' and SIGMAX0.0, 1MAXITSMAXITN.
14:   MONIT – INTEGERInput
On entry: if MONIT>0, the frequency at which a monitoring step is executed by F11GEF: the current solution and residual iterates will be returned by F11GEF and a call to F11GFF made possible every MONIT iterations, starting from the (MONIT)th. 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: MONITMAXITN.
15:   LWREQ – INTEGEROutput
On exit: the minimum amount of workspace required by F11GEF. (See also Section 5 in F11GEF.)
16:   WORK(LWORK) – REAL (KIND=nag_wp) arrayCommunication Array
On exit: the array WORK is initialized by F11GDF. It must not be modified before calling the next routine in the suite, namely F11GEF.
17:   LWORK – INTEGERInput
On entry: the dimension of the array WORK as declared in the (sub)program from which F11GDF is called.
Constraint: LWORK120.
Note:  although the minimum value of LWORK ensures the correct functioning of F11GDF, a larger value is required by the other routines in the suite, namely F11GEF and F11GFF. The required value is as follows:
Method Requirements
CG LWORK=120+5n+p.
SYMMLQ LWORK=120+6n+p,
MINRES LWORK=120+9n,
where
  • p=2*MAXITS+1, when an estimate of σ1A (SIGMAX) is computed;
  • p=0, otherwise.
18:   IFAIL – INTEGERInput/Output
On entry: IFAIL must be set to 0, -1​ 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​ 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 -1​ or ​1 is used it is essential to test the value of IFAIL on exit.
On exit: IFAIL=0 unless the routine detects an error or a warning has been flagged (see Section 6).

6  Error Indicators and Warnings

If on entry IFAIL=0 or -1, explanatory error messages are output on the current error message unit (as defined by X04AAF).
Errors or warnings detected by the routine:
IFAIL=-i
On entry, the ith argument had an illegal value.
IFAIL=1
F11GDF has been called out of sequence.

7  Accuracy

Not applicable.

8  Further Comments

When σ1A- is not supplied (SIGMAX0.0) but it is required, it is estimated by F11GEF using either of the two methods described in Section 3, as specified by the parameter SIGCMP. In particular, if SIGCMP='S', then the computation of σ1A- is deemed to have converged when the differences between three successive values of σ1Tk differ, in a relative sense, by less than the tolerance SIGTOL, i.e., when
max σ1k-σ1k-1 σ1k , ​ σ1k-σ1k-2 σ1k SIGTOL.
The computation of σ1A- is also terminated when the iteration count exceeds the maximum value allowed, i.e., kMAXITS.
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, σ1A- usually converges within very few iterations.

9  Example

This example solves a symmetric 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).

9.1  Program Text

Program Text (f11gdfe.f90)

9.2  Program Data

Program Data (f11gdfe.d)

9.3  Program Results

Program Results (f11gdfe.r)


F11GDF (PDF version)
F11 Chapter Contents
F11 Chapter Introduction
NAG Library Manual

© The Numerical Algorithms Group Ltd, Oxford, UK. 2012