F02FJF (PDF version)
F02 Chapter Contents
F02 Chapter Introduction
NAG Library Manual

NAG Library Routine Document

F02FJF

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

F02FJF finds eigenvalues and eigenvectors of a real sparse symmetric or generalized symmetric eigenvalue problem.

2  Specification

SUBROUTINE F02FJF ( N, M, K, NOITS, TOL, DOT, IMAGE, MONIT, NOVECS, X, LDX, D, WORK, LWORK, RUSER, LRUSER, IUSER, LIUSER, IFAIL)
INTEGER  N, M, K, NOITS, NOVECS, LDX, LWORK, LRUSER, IUSER(LIUSER), LIUSER, IFAIL
REAL (KIND=nag_wp)  TOL, DOT, X(LDX,K), D(K), WORK(LWORK), RUSER(LRUSER)
EXTERNAL  DOT, IMAGE, MONIT

3  Description

F02FJF finds the m eigenvalues of largest absolute value and the corresponding eigenvectors for the real eigenvalue problem
Cx=λ x (1)
where C is an n by n matrix such that
BC=CTB (2)
for a given positive definite matrix B. C is said to be B-symmetric. Different specifications of C allow for the solution of a variety of eigenvalue problems. For example, when
C=A  and  B=I  where  A=AT
the routine finds the m eigenvalues of largest absolute magnitude for the standard symmetric eigenvalue problem
Ax=λx. (3)
The routine is intended for the case where A is sparse.
As a second example, when
C=B-1A
where
A=AT
the routine finds the m eigenvalues of largest absolute magnitude for the generalized symmetric eigenvalue problem
Ax=λBx. (4)
The routine is intended for the case where A and B are sparse.
The routine does not require C explicitly, but C is specified via IMAGE which, given an n-element vector z, computes the image w given by
w=Cz.
For instance, in the above example, where C=B-1A, IMAGE will need to solve the positive definite system of equations Bw=Az for w.
To find the m eigenvalues of smallest absolute magnitude of (3) we can choose C=A-1 and hence find the reciprocals of the required eigenvalues, so that IMAGE will need to solve Aw=z for w, and correspondingly for (4) we can choose C=A-1B and solve Aw=Bz for w.
A table of examples of choice of IMAGE is given in Table 1. It should be remembered that the routine also returns the corresponding eigenvectors and that B is positive definite. Throughout A is assumed to be symmetric and, where necessary, nonsingularity is also assumed.
Eigenvalues
Required
Problem
  Ax=λx B=I Ax=λBx ABx=λx
Largest Compute w=Az Solve Bw=Az Compute w=ABz
Smallest (Find 1/λ) Solve Aw=z Solve Aw=Bz Solve Av=z, Bw=v
Furthest from σ 
(Find λ-σ)
Compute
w=A-σIz
Solve Bw=A-σBz Compute
w=AB-σIz
Closest to σ 
(Find 1/λ-σ)
Solve A-σIw=z Solve A-σBw=Bz Solve AB-σIw=z
Table 1
The Requirement of IMAGE for Various Problems.
The matrix B also need not be supplied explicitly, but is specified via DOT which, given n-element vectors z and w, computes the generalized dot product wTBz.
F02FJF is based upon routine SIMITZ (see Nikolai (1979)), which is itself a derivative of the Algol procedure ritzit (see Rutishauser (1970)), and uses the method of simultaneous (subspace) iteration. (See Parlett (1998) for a description, analysis and advice on the use of the method.)
The routine performs simultaneous iteration on k>m vectors. Initial estimates to pk eigenvectors, corresponding to the p eigenvalues of C of largest absolute value, may be supplied to F02FJF. When possible k should be chosen so that the kth eigenvalue is not too close to the m required eigenvalues, but if k is initially chosen too small then F02FJF may be re-entered, supplying approximations to the k eigenvectors found so far and with k then increased.
At each major iteration F02FJF solves an r by r (rk) eigenvalue sub-problem in order to obtain an approximation to the eigenvalues for which convergence has not yet occurred. This approximation is refined by Chebyshev acceleration.

4  References

Nikolai P J (1979) Algorithm 538: Eigenvectors and eigenvalues of real generalized symmetric matrices by simultaneous iteration ACM Trans. Math. Software 5 118–125
Parlett B N (1998) The Symmetric Eigenvalue Problem SIAM, Philadelphia
Rutishauser H (1969) Computational aspects of F L Bauer's simultaneous iteration method Numer. Math. 13 4–13
Rutishauser H (1970) Simultaneous iteration method for symmetric matrices Numer. Math. 16 205–223

5  Parameters

1:     N – INTEGERInput
On entry: n, the order of the matrix C.
Constraint: N1.
2:     M – INTEGERInput/Output
On entry: m, the number of eigenvalues required.
Constraint: M1.
On exit: m, the number of eigenvalues actually found. It is equal to m if IFAIL=0 on exit, and is less than m if IFAIL=2, 3 or 4. See Sections 6 and 8 for further information.
3:     K – INTEGERInput
On entry: the number of simultaneous iteration vectors to be used. Too small a value of K may inhibit convergence, while a larger value of K incurs additional storage and additional work per iteration.
Suggested value: K=M+4 will often be a reasonable choice in the absence of better information.
Constraint: M<KN.
4:     NOITS – INTEGERInput/Output
On entry: the maximum number of major iterations (eigenvalue sub-problems) to be performed. If NOITS0, the value 100 is used in place of NOITS.
On exit: the number of iterations actually performed.
5:     TOL – REAL (KIND=nag_wp)Input
On entry: a relative tolerance to be used in accepting eigenvalues and eigenvectors. If the eigenvalues are required to about t significant figures, TOL should be set to about 10-t. di is accepted as an eigenvalue as soon as two successive approximations to di differ by less than d~i×TOL/10, where d~i is the latest approximation to di. Once an eigenvalue has been accepted, an eigenvector is accepted as soon as difi/di-dk<TOL, where fi is the normalized residual of the current approximation to the eigenvector (see Section 8 for further information). The values of the fi and di can be printed from MONIT. If TOL is supplied outside the range (ε,1.0), where ε is the machine precision, the value ε is used in place of TOL.
6:     DOT – REAL (KIND=nag_wp) FUNCTION, supplied by the user.External Procedure
DOT must return the value wTBz for given vectors w and z. For the standard eigenvalue problem, where B=I, DOT must return the dot product wTz.
The specification of DOT is:
FUNCTION DOT ( IFLAG, N, Z, W, RUSER, LRUSER, IUSER, LIUSER)
REAL (KIND=nag_wp) DOT
INTEGER  IFLAG, N, LRUSER, IUSER(LIUSER), LIUSER
REAL (KIND=nag_wp)  Z(N), W(N), RUSER(LRUSER)
1:     IFLAG – INTEGERInput/Output
On entry: is always non-negative.
On exit: may be used as a flag to indicate a failure in the computation of wTBz. If IFLAG is negative on exit from DOT, F02FJF will exit immediately with IFAIL set to IFLAG. Note that in this case DOT must still be assigned a value.
2:     N – INTEGERInput
On entry: the number of elements in the vectors z and w and the order of the matrix B.
3:     Z(N) – REAL (KIND=nag_wp) arrayInput
On entry: the vector z for which wTBz is required.
4:     W(N) – REAL (KIND=nag_wp) arrayInput
On entry: the vector w for which wTBz is required.
5:     RUSER(LRUSER) – REAL (KIND=nag_wp) arrayUser Workspace
DOT is called with the parameter RUSER as supplied to F02FJF. You are free to use the array RUSER to supply information to DOT as an alternative to using COMMON global variables.
6:     LRUSER – INTEGERInput
On entry: the dimension of the array RUSER as declared in the (sub)program from which F02FJF is called.
7:     IUSER(LIUSER) – INTEGER arrayUser Workspace
DOT is called with the parameter IUSER as supplied to F02FJF. You are free to use the array IUSER to supply information to DOT as an alternative to using COMMON global variables.
8:     LIUSER – INTEGERInput
On entry: the dimension of the array IUSER as declared in the (sub)program from which F02FJF is called.
DOT must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which F02FJF is called. Parameters denoted as Input must not be changed by this procedure.
7:     IMAGE – SUBROUTINE, supplied by the user.External Procedure
IMAGE must return the vector w=Cz for a given vector z.
The specification of IMAGE is:
SUBROUTINE IMAGE ( IFLAG, N, Z, W, RUSER, LRUSER, IUSER, LIUSER)
INTEGER  IFLAG, N, LRUSER, IUSER(LIUSER), LIUSER
REAL (KIND=nag_wp)  Z(N), W(N), RUSER(LRUSER)
1:     IFLAG – INTEGERInput/Output
On entry: is always non-negative.
On exit: may be used as a flag to indicate a failure in the computation of w. If IFLAG is negative on exit from IMAGE, F02FJF will exit immediately with IFAIL set to IFLAG.
2:     N – INTEGERInput
On entry: n, the number of elements in the vectors w and z, and the order of the matrix C.
3:     Z(N) – REAL (KIND=nag_wp) arrayInput
On entry: the vector z for which Cz is required.
4:     W(N) – REAL (KIND=nag_wp) arrayOutput
On exit: the vector w=Cz.
5:     RUSER(LRUSER) – REAL (KIND=nag_wp) arrayUser Workspace
IMAGE is called with the parameter RUSER as supplied to F02FJF. You are free to use the array RUSER to supply information to IMAGE as an alternative to using COMMON global variables.
6:     LRUSER – INTEGERInput
On entry: the dimension of the array RUSER as declared in the (sub)program from which F02FJF is called.
7:     IUSER(LIUSER) – INTEGER arrayUser Workspace
IMAGE is called with the parameter IUSER as supplied to F02FJF. You are free to use the array IUSER to supply information to IMAGE as an alternative to using COMMON global variables.
8:     LIUSER – INTEGERInput
On entry: the dimension of the array IUSER as declared in the (sub)program from which F02FJF is called.
IMAGE must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which F02FJF is called. Parameters denoted as Input must not be changed by this procedure.
8:     MONIT – SUBROUTINE, supplied by the NAG Library or the user.External Procedure
MONIT is used to monitor the progress of F02FJF. MONIT may be the dummy subroutine F02FJZ if no monitoring is actually required. (F02FJZ is included in the NAG Library.) MONIT is called after the solution of each eigenvalue sub-problem and also just prior to return from F02FJF. The parameters ISTATE and NEXTIT allow selective printing by MONIT.
The specification of MONIT is:
SUBROUTINE MONIT ( ISTATE, NEXTIT, NEVALS, NEVECS, K, F, D)
INTEGER  ISTATE, NEXTIT, NEVALS, NEVECS, K
REAL (KIND=nag_wp)  F(K), D(K)
1:     ISTATE – INTEGERInput
On entry: specifies the state of F02FJF.
ISTATE=0
No eigenvalue or eigenvector has just been accepted.
ISTATE=1
One or more eigenvalues have been accepted since the last call to MONIT.
ISTATE=2
One or more eigenvectors have been accepted since the last call to MONIT.
ISTATE=3
One or more eigenvalues and eigenvectors have been accepted since the last call to MONIT.
ISTATE=4
Return from F02FJF is about to occur.
2:     NEXTIT – INTEGERInput
On entry: the number of the next iteration.
3:     NEVALS – INTEGERInput
On entry: the number of eigenvalues accepted so far.
4:     NEVECS – INTEGERInput
On entry: the number of eigenvectors accepted so far.
5:     K – INTEGERInput
On entry: k, the number of simultaneous iteration vectors.
6:     F(K) – REAL (KIND=nag_wp) arrayInput
On entry: a vector of error quantities measuring the state of convergence of the simultaneous iteration vectors. See TOL and Section 8 for further details. Each element of F is initially set to the value 4.0 and an element remains at 4.0 until the corresponding vector is tested.
7:     D(K) – REAL (KIND=nag_wp) arrayInput
On entry: Di contains the latest approximation to the absolute value of the ith eigenvalue of C.
MONIT must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which F02FJF is called. Parameters denoted as Input must not be changed by this procedure.
9:     NOVECS – INTEGERInput
On entry: the number of approximate vectors that are being supplied in X. If NOVECS is outside the range 0,K, the value 0 is used in place of NOVECS.
10:   X(LDX,K) – REAL (KIND=nag_wp) arrayInput/Output
On entry: if 0<NOVECSK, the first NOVECS columns of X must contain approximations to the eigenvectors corresponding to the NOVECS eigenvalues of largest absolute value of C. Supplying approximate eigenvectors can be useful when reasonable approximations are known, or when F02FJF is being restarted with a larger value of K. Otherwise it is not necessary to supply approximate vectors, as simultaneous iteration vectors will be generated randomly by F02FJF.
On exit: if IFAIL=0, 2, 3 or 4, the first m columns contain the eigenvectors corresponding to the eigenvalues returned in the first m elements of D; and the next k-m-1 columns contain approximations to the eigenvectors corresponding to the approximate eigenvalues returned in the next k-m-1 elements of D. Here m is the value returned in M, the number of eigenvalues actually found. The kth column is used as workspace.
11:   LDX – INTEGERInput
On entry: the first dimension of the array X as declared in the (sub)program from which F02FJF is called.
Constraint: LDXN.
12:   D(K) – REAL (KIND=nag_wp) arrayOutput
On exit: if IFAIL=0, 2, 3 or 4, the first m elements contain the first m eigenvalues in decreasing order of magnitude; and the next k-m-1 elements contain approximations to the next k-m-1 eigenvalues. Here m is the value returned in M, the number of eigenvalues actually found. Dk contains the value e where -e,e is the latest interval over which Chebyshev acceleration is performed.
13:   WORK(LWORK) – REAL (KIND=nag_wp) arrayWorkspace
14:   LWORK – INTEGERInput
On entry: the dimension of the array WORK as declared in the (sub)program from which F02FJF is called.
Constraint: LWORK3×K+maxK×K,2×N.
15:   RUSER(LRUSER) – REAL (KIND=nag_wp) arrayUser Workspace
RUSER is not used by F02FJF, but is passed directly to DOT and IMAGE and may be used to pass information to these routines as an alternative to using COMMON global variables.
16:   LRUSER – INTEGERInput
On entry: the dimension of the array RUSER as declared in the (sub)program from which F02FJF is called.
Constraint: LRUSER1.
17:   IUSER(LIUSER) – INTEGER arrayUser Workspace
IUSER is not used by F02FJF, but is passed directly to DOT and IMAGE and may be used to pass information to these routines as an alternative to using COMMON global variables.
18:   LIUSER – INTEGERInput
On entry: the dimension of the array IUSER as declared in the (sub)program from which F02FJF is called.
Constraint: LIUSER1.
19:   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, because for this routine the values of the output parameters may be useful even if IFAIL0 on exit, the recommended value is -1. 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<0
A negative value of IFAIL indicates an exit from F02FJF because you have set IFLAG negative in DOT or IMAGE. The value of IFAIL will be the same as your setting of IFLAG.
IFAIL=1
On entry,N<1,
orM<1,
orMK,
orK>N,
orLDX<N,
orLWORK<3×K+maxK×K,2×N,
orLRUSER<1,
orLIUSER<1.
IFAIL=2
Not all the requested eigenvalues and vectors have been obtained. Approximations to the rth eigenvalue are oscillating rapidly indicating that severe cancellation is occurring in the rth eigenvector and so M is returned as r-1. A restart with a larger value of K may permit convergence.
IFAIL=3
Not all the requested eigenvalues and vectors have been obtained. The rate of convergence of the remaining eigenvectors suggests that more than NOITS iterations would be required and so the input value of M has been reduced. A restart with a larger value of K may permit convergence.
IFAIL=4
Not all the requested eigenvalues and vectors have been obtained. NOITS iterations have been performed. A restart, possibly with a larger value of K, may permit convergence.
IFAIL=5
This error is very unlikely to occur, but indicates that convergence of the eigenvalue sub-problem has not taken place. Restarting with a different set of approximate vectors may allow convergence. If this error occurs you should check carefully that F02FJF is being called correctly.

7  Accuracy

Eigenvalues and eigenvectors will normally be computed to the accuracy requested by the parameter TOL, but eigenvectors corresponding to small or to close eigenvalues may not always be computed to the accuracy requested by the parameter TOL. Use of the MONIT to monitor acceptance of eigenvalues and eigenvectors is recommended.

8  Further Comments

The time taken by F02FJF will be principally determined by the time taken to solve the eigenvalue sub-problem and the time taken by DOT and IMAGE. The time taken to solve an eigenvalue sub-problem is approximately proportional to nk2. It is important to be aware that several calls to DOT and IMAGE may occur on each major iteration.
As can be seen from Table 1, many applications of F02FJF will require the IMAGE to solve a system of linear equations. For example, to find the smallest eigenvalues of Ax=λ Bx, IMAGE needs to solve equations of the form Aw=Bz for w and routines from Chapters F01 and F04 will frequently be useful in this context. In particular, if A is a positive definite variable band matrix, F04MCF may be used after A has been factorized by F01MCF. Thus factorization need be performed only once prior to calling F02FJF. An illustration of this type of use is given in the example program.
An approximation d~h, to the ith eigenvalue, is accepted as soon as d~h and the previous approximation differ by less than d~h×TOL/ 10. Eigenvectors are accepted in groups corresponding to clusters of eigenvalues that are equal, or nearly equal, in absolute value and that have already been accepted. If dr is the last eigenvalue in such a group and we define the residual rj as
rj=Cxj-yr
where yr is the projection of Cxj, with respect to B, onto the space spanned by x1,x2,, xr, and xj is the current approximation to the jth eigenvector, then the value fi returned in MONIT is given by
fi = maxrjB / CxjB xB2 = xTBx
and each vector in the group is accepted as an eigenvector if
dr fr/dr-e<TOL,
where e is the current approximation to d~k. The values of the fi are systematically increased if the convergence criteria appear to be too strict. See Rutishauser (1970) for further details.
The algorithm implemented by F02FJF differs slightly from SIMITZ (see Nikolai (1979)) in that the eigenvalue sub-problem is solved using the singular value decomposition of the upper triangular matrix R of the Gram–Schmidt factorization of Cxr, rather than forming RTR.

9  Example

This example finds the four eigenvalues of smallest absolute value and corresponding eigenvectors for the generalized symmetric eigenvalue problem Ax=λBx, where A and B are the 16 by 16 matrices
A=-14 -4 1 1 1 -4 1 1 1 -4 1 1 1 -4 1 1 1 1 -4 1 1 1 1 -4 1 1 1 1 -4 1 1 1 1 -4 1 1 1 1 -4 1 1 1 1 -4 1 1 1 1 -4 1 1 1 1 -4 1 1 1 1 -4 1 1 1 -4 1 1 1 -4 1 1 1 -4
B=-12 -2 1 1 -2 1 1 -2 1 1 -2 1 1 -2 1 1 -2 1 1 -2 1 1 -2 1 1 -2 1 1 -2 1 1 -2 1 1 -2 1 1 -2 1 1 -2 1 1 -2 1 1 -2
TOL is taken as 0.0001 and 6 iteration vectors are used. F11JAF is used to factorize the matrix A, prior to calling F02FJF, and F11JCF is used within IMAGE to solve the equations Aw=Bz for w. Details of the factorization of A are passed from F11JAF to F11JCF by means of the COMMON block BLOCK1.
Output from MONIT occurs each time ISTATE is nonzero. Note that the required eigenvalues are the reciprocals of the eigenvalues returned by F02FJF.

9.1  Program Text

Program Text (f02fjfe.f90)

9.2  Program Data

Program Data (f02fjfe.d)

9.3  Program Results

Program Results (f02fjfe.r)


F02FJF (PDF version)
F02 Chapter Contents
F02 Chapter Introduction
NAG Library Manual

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