NAG CL Interface
f11gec (real_​symm_​basic_​solver)

1 Purpose

f11gec is an iterative solver for a symmetric system of simultaneous linear equations; f11gec is the second in a suite of three functions, where the first function, f11gdc, must be called prior to f11gec to set up the suite, and the third function in the suite, f11gfc, can be used to return additional information about the computation.
These three functions are suitable for the solution of large sparse symmetric systems of equations.

2 Specification

#include <nag.h>
void  f11gec (Integer *irevcm, double u[], double v[], const double wgt[], double work[], Integer lwork, NagError *fail)
The function may be called by the names: f11gec, nag_sparse_real_symm_basic_solver or nag_sparse_sym_basic_solver.

3 Description

f11gec 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 f11gdc.
f11gec can solve the system after the first function in the suite, f11gdc, has been called to initialize the computation and specify the method of solution. The third function in the suite, f11gfc, can be used to return additional information generated by the computation during monitoring steps and after f11gec has completed its tasks.
f11gec uses reverse communication, i.e., f11gec returns repeatedly to the calling program with the argument irevcm (see Section 5) 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. 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. 2.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 functions 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 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 Arguments

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.
1: irevcm Integer * Input/Output
On initial entry: irevcm=0, otherwise an error condition will be raised.
On intermediate re-entry: must either be unchanged from its previous exit value, or can have one of the following values.
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. f11gec will then return with the termination code irevcm=4. Note that before calling f11gec with irevcm=5 the calling program must have performed the tasks required by the value of irevcm returned by the previous call to f11gec, otherwise subsequently returned values may be invalid.
irevcm=6
Immediate termination: f11gec will return immediately with termination code 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. f11gec will then return with the termination code 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.
On intermediate exit: has the following meanings.
irevcm=1
The calling program must compute the matrix-vector product v=Au, where u and v are stored in u and v, respectively.
irevcm=2
The calling program must solve the preconditioning equation Mv=u, where u and v are stored in u and v, respectively.
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 f11gfc can be called at this step.
On final exit: if irevcm=4, f11gec has completed its tasks. The value of fail.code determines whether the iteration has been successfully completed, errors have been detected or the calling program has requested termination.
Constraint: on initial entry, irevcm=0; on re-entry, either irevcm must remain unchanged or be reset to irevcm=5 or 6.
Note: any values you return to f11gec as part of the reverse communication procedure should not include floating-point NaN (Not a Number) or infinity values, since these are not handled by f11gec. If your code inadvertently does return any NaNs or infinities, f11gec is likely to produce unexpected results.
2: u[dim] double Input/Output
Note: the dimension, dim, of the array u must be at least n.
On initial entry: an initial estimate, x0, of the solution of the system of equations Ax=b.
On intermediate re-entry: must remain unchanged.
On intermediate exit: the returned value of irevcm determines the contents of u in the following way.
If irevcm=1 or 2, u holds the vector u on which the operation specified by irevcm is to be carried out.
If irevcm=3, u holds the current iterate of the solution vector.
On final exit: if after the first call fail.code= NE_INT or NE_OUT_OF_SEQUENCE, the array u is unchanged from the initial entry to f11gec. If after an intermediate call fail.code= NE_INT or NE_OUT_OF_SEQUENCE, the array u is unchanged from the last entry to f11gec. Otherwise, u holds the last iterate of the solution of the system of equations, for all returned values of fail.code.
3: v[dim] double Input/Output
Note: the dimension, dim, of the array v must be at least 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 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 f11gec.
If irevcm=3, v must remain unchanged.
On intermediate exit: if 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 after the first call fail.code= NE_INT or NE_OUT_OF_SEQUENCE, the array v is unchanged from the initial entry to f11gec. If after an intermediate call fail.code= NE_INT or NE_OUT_OF_SEQUENCE, the array v is unchanged from the last entry to f11gec. Otherwise, v stores the last iterate of the residual vector unless the Lanczos method (SYMMLQ) was used and fail.code= NE_COEFF_NOT_POS_DEF, NE_CONVERGENCE, NE_PRECOND_NOT_POS_DEF, NE_SINGULAR, NE_USER_STOP or NE_WEIGHT_ZERO, in which case v is set to 0.0.
4: wgt[dim] const double Input
Note: the dimension, dim, of the array wgt must be at least max1,n.
On entry: the user-supplied weights, if these are to be used in the computation of the vector norms in the termination criterion (see Sections 3 and 5 in f11gdc).
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] double Communication Array
On initial entry: the array work as returned by f11gdc (see also Section 5 in f11gdc).
On intermediate re-entry: must remain unchanged.
6: lwork Integer Input
On initial entry: the dimension of the array work (see also Section 3 in f11gdc). The required amount of workspace 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.
Constraint: lworklwreq, where lwreq is returned by f11gdc.
7: fail NagError * Input/Output
The NAG error argument (see Section 7 in the Introduction to the NAG Library CL Interface).
Error details reported in fail are only valid on final exit. On intermediate exit, returned values of fail should be ignored.

6 Error Indicators and Warnings

NE_ACCURACY
fail.errnum=1
User-requested termination: the required accuracy could not be obtained. However, a reasonable accuracy may have been achieved.
fail.errnum=2
The required accuracy could not be obtained. However, a reasonable accuracy may have been achieved.
NE_ALLOC_FAIL
Dynamic memory allocation failed.
See Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.
NE_BAD_PARAM
On entry, argument value had an illegal value.
NE_COEFF_NOT_POS_DEF
The matrix of the coefficients A appears not to be positive definite. The computation cannot continue.
NE_CONVERGENCE
The solution has not converged after value iterations.
User-requested tidy termination. The solution has not converged after value iterations.
NE_INT
On entry, lwork=value.
Constraint: lworklwreq, where lwreq is returned by f11gdc.
On initial entry, irevcm=value.
Constraint: irevcm=0.
On intermediate re-entry, irevcm=value.
Constraint: either irevcm must be unchanged from its previous exit value or irevcm=5 or 6.
NE_INTERNAL_ERROR
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
See Section 7.5 in the Introduction to the NAG Library CL Interface for further information.
NE_NO_LICENCE
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library CL Interface for further information.
NE_OUT_OF_SEQUENCE
Either f11gdc was not called before calling this function or it has returned an error.
f11gec has already completed its tasks. You need to set a new problem.
NE_PRECOND_NOT_POS_DEF
The preconditioner appears not to be positive definite. The computation cannot continue.
NE_SINGULAR
The matrix of the coefficients A appears to be singular. The computation cannot continue.
NE_USER_STOP
User-requested immediate termination.
NE_WEIGHT_ZERO
The weights in array wgt are all zero.

7 Accuracy

On completion, i.e., irevcm=4 on exit, the arrays u and v will return the solution and residual vectors, xk and rk=b-Axk, respectively, at the kth 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 Section 3 in f11gdc. The computed values of the left- and right-hand sides of the termination criterion selected can be obtained by a call to f11gfc.

8 Parallelism and Performance

f11gec is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
f11gec makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.
Please consult the X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this function. Please also consult the Users' Note for your implementation for any additional implementation-specific information.

9 Further Comments

The number of operations carried out by f11gec 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 f11gec for each iteration is approximately proportional to 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 A¯=E-1AE-T.
Additional matrix-vector products are required for the computation of A1=A, when this has not been supplied to f11gdc and is required by the termination criterion employed.
The number of operations required to compute σ1A¯ is negligible for reasonable values of sigtol and maxits (see Sections 5 and 9 in f11gdc).
If the termination criterion rkp τ bp+Ap × xkp is used (see Section 3 in f11gdc) and x0xk, so that because of loss of significant digits the required accuracy could not be obtained, the iteration is restarted automatically at some suitable point: f11gec sets x0=xk 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 x0 which is as close to the true solution x~ as can be estimated. Otherwise, the iteration should start from x0=0.

10 Example

See Section 10 in f11gdc.