NAG Library Routine Document
f02fjf (real_symm_sparse_eigsys)
1
Purpose
f02fjf finds eigenvalues and eigenvectors of a real sparse symmetric or generalized symmetric eigenvalue problem.
2
Specification
Fortran Interface
Subroutine f02fjf ( 
n, m, k, noits, tol, dot, image, monit, novecs, x, ldx, d, work, lwork, ruser, lruser, iuser, liuser, ifail) 
Integer, Intent (In)  ::  n, k, novecs, ldx, lwork, lruser, liuser  Integer, Intent (Inout)  ::  m, noits, iuser(liuser), ifail  Real (Kind=nag_wp), External  ::  dot  Real (Kind=nag_wp), Intent (In)  ::  tol  Real (Kind=nag_wp), Intent (Inout)  ::  x(ldx,k), ruser(lruser)  Real (Kind=nag_wp), Intent (Out)  ::  d(k), work(lwork)  External  ::  image, monit 

C Header Interface
#include nagmk26.h
void 
f02fjf_ (const Integer *n, Integer *m, const Integer *k, Integer *noits, const double *tol, double (NAG_CALL *dot)(Integer *iflag, const Integer *n, const double z[], const double w[], double ruser[], const Integer *lruser, Integer iuser[], const Integer *liuser), void (NAG_CALL *image)(Integer *iflag, const Integer *n, const double z[], double w[], double ruser[], const Integer *lruser, Integer iuser[], const Integer *liuser), void (NAG_CALL *monit)(const Integer *istate, const Integer *nextit, const Integer *nevals, const Integer *nevecs, const Integer *k, const double f[], const double d[]), const Integer *novecs, double x[], const Integer *ldx, double d[], double work[], const Integer *lwork, double ruser[], const Integer *lruser, Integer iuser[], const Integer *liuser, Integer *ifail) 

3
Description
f02fjf finds the
$m$ eigenvalues of largest absolute value and the corresponding eigenvectors for the real eigenvalue problem
where
$C$ is an
$n$ by
$n$ matrix such that
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
the routine finds the
$m$ eigenvalues of largest absolute magnitude for the standard symmetric eigenvalue problem
The routine is intended for the case where
$A$ is sparse.
As a second example, when
where
the routine finds the
$m$ eigenvalues of largest absolute magnitude for the generalized symmetric eigenvalue problem
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
For instance, in the above example, where
$C={B}^{1}A$,
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}^{1}B$ 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=\lambda x\left(B=I\right)$ 
$Ax=\lambda Bx$ 
$ABx=\lambda x$ 
Largest 
Compute $w=Az$ 
Solve $Bw=Az$ 
Compute $w=ABz$ 
Smallest (Find $1/\lambda $) 
Solve $Aw=z$ 
Solve $Aw=Bz$ 
Solve $Av=z$, $Bw=v$ 
Furthest from $\sigma $
(Find $\lambda \sigma $) 
Compute
$w=\left(A\sigma I\right)z$ 
Solve $Bw=\left(A\sigma B\right)z$ 
Compute
$w=\left(AB\sigma I\right)z$ 
Closest to $\sigma $
(Find $1/\left(\lambda \sigma \right)$) 
Solve $\left(A\sigma I\right)w=z$ 
Solve $\left(A\sigma B\right)w=Bz$ 
Solve $\left(AB\sigma I\right)w=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
${w}^{\mathrm{T}}Bz$.
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 $p\le k$ 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 $k$th eigenvalue is not too close to the $m$ required eigenvalues, but if $k$ is initially chosen too small then f02fjf may be reentered, supplying approximations to the $k$ eigenvectors found so far and with $k$ then increased.
At each major iteration f02fjf solves an $r$ by $r$ ($r\le k$) eigenvalue subproblem 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
Arguments
 1: $\mathbf{n}$ – IntegerInput

On entry: $n$, the order of the matrix $C$.
Constraint:
${\mathbf{n}}\ge 1$.
 2: $\mathbf{m}$ – IntegerInput/Output

On entry: $m$, the number of eigenvalues required.
Constraint:
${\mathbf{m}}\ge 1$.
On exit:
${m}^{\prime}$, the number of eigenvalues actually found. It is equal to
$m$ if
${\mathbf{ifail}}={\mathbf{0}}$ on exit, and is less than
$m$ if
${\mathbf{ifail}}={\mathbf{2}}$,
${\mathbf{3}}$ or
${\mathbf{4}}$. See
Sections 6 and
9 for further information.
 3: $\mathbf{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:
${\mathbf{k}}={\mathbf{m}}+4$ will often be a reasonable choice in the absence of better information.
Constraint:
${\mathbf{m}}<{\mathbf{k}}\le {\mathbf{n}}$.
 4: $\mathbf{noits}$ – IntegerInput/Output

On entry: the maximum number of major iterations (eigenvalue subproblems) to be performed. If
${\mathbf{noits}}\le 0$, the value
$100$ is used in place of
noits.
On exit: the number of iterations actually performed.
 5: $\mathbf{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}$.
${d}_{i}$ is accepted as an eigenvalue as soon as two successive approximations to
${d}_{i}$ differ by less than
$\left(\left{\stackrel{~}{d}}_{i}\right\times {\mathbf{tol}}\right)/10$, where
${\stackrel{~}{d}}_{i}$ is the latest approximation to
${d}_{i}$. Once an eigenvalue has been accepted, an eigenvector is accepted as soon as
$\left({d}_{i}{f}_{i}\right)/\left({d}_{i}{d}_{k}\right)<{\mathbf{tol}}$, where
${f}_{i}$ is the normalized residual of the current approximation to the eigenvector (see
Section 9 for further information). The values of the
${f}_{i}$ and
${d}_{i}$ can be printed from
monit. If
tol is supplied outside the range (
$\epsilon ,1.0$), where
$\epsilon $ is the
machine precision, the value
$\epsilon $ is used in place of
tol.
 6: $\mathbf{dot}$ – real (Kind=nag_wp) Function, supplied by the user.External Procedure

dot must return the value
${w}^{\mathrm{T}}Bz$ for given vectors
$w$ and
$z$. For the standard eigenvalue problem, where
$B=I$,
dot must return the dot product
${w}^{\mathrm{T}}z$.
The specification of
dot is:
Fortran Interface
Real (Kind=nag_wp)  ::  dot  Integer, Intent (In)  ::  n, lruser, liuser  Integer, Intent (Inout)  ::  iflag, iuser(liuser)  Real (Kind=nag_wp), Intent (In)  ::  z(n), w(n)  Real (Kind=nag_wp), Intent (Inout)  ::  ruser(lruser) 

C Header Interface
#include nagmk26.h
double 
dot (Integer *iflag, const Integer *n, const double z[], const double w[], double ruser[], const Integer *lruser, Integer iuser[], const Integer *liuser) 

 1: $\mathbf{iflag}$ – IntegerInput/Output

On entry: is always nonnegative.
On exit: may be used as a flag to indicate a failure in the computation of
${w}^{\mathrm{T}}Bz$. 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: $\mathbf{n}$ – IntegerInput

On entry: the number of elements in the vectors $z$ and $w$ and the order of the matrix $B$.
 3: $\mathbf{z}\left({\mathbf{n}}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: the vector $z$ for which ${w}^{\mathrm{T}}Bz$ is required.
 4: $\mathbf{w}\left({\mathbf{n}}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: the vector $w$ for which ${w}^{\mathrm{T}}Bz$ is required.
 5: $\mathbf{ruser}\left({\mathbf{lruser}}\right)$ – Real (Kind=nag_wp) arrayUser Workspace

dot is called with the argument
ruser as supplied to
f02fjf. You should use the array
ruser to supply information to
dot.
 6: $\mathbf{lruser}$ – IntegerInput

On entry: the dimension of the array
ruser as declared in the (sub)program from which
f02fjf is called.
 7: $\mathbf{iuser}\left({\mathbf{liuser}}\right)$ – Integer arrayUser Workspace

dot is called with the argument
iuser as supplied to
f02fjf. You should use the array
iuser to supply information to
dot.
 8: $\mathbf{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. Arguments denoted as
Input must
not be changed by this procedure.
Note: dot should not return floatingpoint NaN (Not a Number) or infinity values, since these are not handled by
f02fjf. If your code inadvertently
does return any NaNs or infinities,
f02fjf is likely to produce unexpected results.
 7: $\mathbf{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:
Fortran Interface
Integer, Intent (In)  ::  n, lruser, liuser  Integer, Intent (Inout)  ::  iflag, iuser(liuser)  Real (Kind=nag_wp), Intent (In)  ::  z(n)  Real (Kind=nag_wp), Intent (Inout)  ::  ruser(lruser)  Real (Kind=nag_wp), Intent (Out)  ::  w(n) 

C Header Interface
#include nagmk26.h
void 
image (Integer *iflag, const Integer *n, const double z[], double w[], double ruser[], const Integer *lruser, Integer iuser[], const Integer *liuser) 

 1: $\mathbf{iflag}$ – IntegerInput/Output

On entry: is always nonnegative.
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: $\mathbf{n}$ – IntegerInput

On entry: $n$, the number of elements in the vectors $w$ and $z$, and the order of the matrix $C$.
 3: $\mathbf{z}\left({\mathbf{n}}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: the vector $z$ for which $Cz$ is required.
 4: $\mathbf{w}\left({\mathbf{n}}\right)$ – Real (Kind=nag_wp) arrayOutput

On exit: the vector $w=Cz$.
 5: $\mathbf{ruser}\left({\mathbf{lruser}}\right)$ – Real (Kind=nag_wp) arrayUser Workspace

image is called with the argument
ruser as supplied to
f02fjf. You should use the array
ruser to supply information to
image.
 6: $\mathbf{lruser}$ – IntegerInput

On entry: the dimension of the array
ruser as declared in the (sub)program from which
f02fjf is called.
 7: $\mathbf{iuser}\left({\mathbf{liuser}}\right)$ – Integer arrayUser Workspace

image is called with the argument
iuser as supplied to
f02fjf. You should use the array
iuser to supply information to
image.
 8: $\mathbf{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. Arguments denoted as
Input must
not be changed by this procedure.
Note: image should not return floatingpoint NaN (Not a Number) or infinity values, since these are not handled by
f02fjf. If your code inadvertently
does return any NaNs or infinities,
f02fjf is likely to produce unexpected results.
 8: $\mathbf{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 subproblem and also just prior to return from
f02fjf. The arguments
istate and
nextit allow selective printing by
monit.
The specification of
monit is:
Fortran Interface
Integer, Intent (In)  ::  istate, nextit, nevals, nevecs, k  Real (Kind=nag_wp), Intent (In)  ::  f(k), d(k) 

C Header Interface
#include nagmk26.h
void 
monit (const Integer *istate, const Integer *nextit, const Integer *nevals, const Integer *nevecs, const Integer *k, const double f[], const double d[]) 

 1: $\mathbf{istate}$ – IntegerInput

On entry: specifies the state of
f02fjf.
 ${\mathbf{istate}}=0$
 No eigenvalue or eigenvector has just been accepted.
 ${\mathbf{istate}}=1$
 One or more eigenvalues have been accepted since the last call to monit.
 ${\mathbf{istate}}=2$
 One or more eigenvectors have been accepted since the last call to monit.
 ${\mathbf{istate}}=3$
 One or more eigenvalues and eigenvectors have been accepted since the last call to monit.
 ${\mathbf{istate}}=4$
 Return from f02fjf is about to occur.
 2: $\mathbf{nextit}$ – IntegerInput

On entry: the number of the next iteration.
 3: $\mathbf{nevals}$ – IntegerInput

On entry: the number of eigenvalues accepted so far.
 4: $\mathbf{nevecs}$ – IntegerInput

On entry: the number of eigenvectors accepted so far.
 5: $\mathbf{k}$ – IntegerInput

On entry: $k$, the number of simultaneous iteration vectors.
 6: $\mathbf{f}\left({\mathbf{k}}\right)$ – 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 9 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: $\mathbf{d}\left({\mathbf{k}}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: ${\mathbf{d}}\left(i\right)$ contains the latest approximation to the absolute value of the $i$th 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. Arguments denoted as
Input must
not be changed by this procedure.
 9: $\mathbf{novecs}$ – IntegerInput

On entry: the number of approximate vectors that are being supplied in
x. If
novecs is outside the range
$\left(0,{\mathbf{k}}\right)$, the value
$0$ is used in place of
novecs.
 10: $\mathbf{x}\left({\mathbf{ldx}},{\mathbf{k}}\right)$ – Real (Kind=nag_wp) arrayInput/Output

On entry: if
$0<{\mathbf{novecs}}\le {\mathbf{k}}$, 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
${\mathbf{ifail}}={\mathbf{0}}$,
${\mathbf{2}}$,
${\mathbf{3}}$ or
${\mathbf{4}}$, the first
${m}^{\prime}$ columns contain the eigenvectors corresponding to the eigenvalues returned in the first
${m}^{\prime}$ elements of
d; and the next
$k{m}^{\prime}1$ columns contain approximations to the eigenvectors corresponding to the approximate eigenvalues returned in the next
$k{m}^{\prime}1$ elements of
d. Here
${m}^{\prime}$ is the value returned in
m, the number of eigenvalues actually found. The
$k$th column is used as workspace.
 11: $\mathbf{ldx}$ – IntegerInput

On entry: the first dimension of the array
x as declared in the (sub)program from which
f02fjf is called.
Constraint:
${\mathbf{ldx}}\ge {\mathbf{n}}$.
 12: $\mathbf{d}\left({\mathbf{k}}\right)$ – Real (Kind=nag_wp) arrayOutput

On exit: if
${\mathbf{ifail}}={\mathbf{0}}$,
${\mathbf{2}}$,
${\mathbf{3}}$ or
${\mathbf{4}}$, the first
${m}^{\prime}$ elements contain the first
${m}^{\prime}$ eigenvalues in decreasing order of magnitude; and the next
$k{m}^{\prime}1$ elements contain approximations to the next
$k{m}^{\prime}1$ eigenvalues. Here
${m}^{\prime}$ is the value returned in
m, the number of eigenvalues actually found.
${\mathbf{d}}\left(k\right)$ contains the value
$e$ where
$\left(e,e\right)$ is the latest interval over which Chebyshev acceleration is performed.
 13: $\mathbf{work}\left({\mathbf{lwork}}\right)$ – Real (Kind=nag_wp) arrayWorkspace
 14: $\mathbf{lwork}$ – IntegerInput

On entry: the dimension of the array
work as declared in the (sub)program from which
f02fjf is called.
Constraint:
${\mathbf{lwork}}\ge 3\times {\mathbf{k}}+\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{k}}\times {\mathbf{k}},2\times {\mathbf{n}}\right)$.
 15: $\mathbf{ruser}\left({\mathbf{lruser}}\right)$ – 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.
 16: $\mathbf{lruser}$ – IntegerInput

On entry: the dimension of the array
ruser as declared in the (sub)program from which
f02fjf is called.
Constraint:
${\mathbf{lruser}}\ge 1$.
 17: $\mathbf{iuser}\left({\mathbf{liuser}}\right)$ – 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.
 18: $\mathbf{liuser}$ – IntegerInput

On entry: the dimension of the array
iuser as declared in the (sub)program from which
f02fjf is called.
Constraint:
${\mathbf{liuser}}\ge 1$.
 19: $\mathbf{ifail}$ – IntegerInput/Output

On entry:
ifail must be set to
$0$,
$1\text{ or}1$. If you are unfamiliar with this argument you should refer to
Section 3.4 in How to Use the NAG Library and its Documentation 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 arguments 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 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}}=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:
 ${\mathbf{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.
 ${\mathbf{ifail}}=1$

On entry,  ${\mathbf{n}}<1$, 
or  ${\mathbf{m}}<1$, 
or  ${\mathbf{m}}\ge {\mathbf{k}}$, 
or  ${\mathbf{k}}>{\mathbf{n}}$, 
or  ${\mathbf{ldx}}<{\mathbf{n}}$, 
or  ${\mathbf{lwork}}<3\times {\mathbf{k}}+\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{k}}\times {\mathbf{k}},2\times {\mathbf{n}}\right)$, 
or  ${\mathbf{lruser}}<1$, 
or  ${\mathbf{liuser}}<1$. 
 ${\mathbf{ifail}}=2$

Not all the requested eigenvalues and vectors have been obtained. Approximations to the
$r$th eigenvalue are oscillating rapidly indicating that severe cancellation is occurring in the
$r$th eigenvector and so
m is returned as
$\left(r1\right)$. A restart with a larger value of
k may permit convergence.
 ${\mathbf{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.
 ${\mathbf{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.
 ${\mathbf{ifail}}=5$

This error is very unlikely to occur, but indicates that convergence of the eigenvalue subproblem 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.
 ${\mathbf{ifail}}=99$
An unexpected error has been triggered by this routine. Please
contact
NAG.
See
Section 3.9 in How to Use the NAG Library and its Documentation for further information.
 ${\mathbf{ifail}}=399$
Your licence key may have expired or may not have been installed correctly.
See
Section 3.8 in How to Use the NAG Library and its Documentation for further information.
 ${\mathbf{ifail}}=999$
Dynamic memory allocation failed.
See
Section 3.7 in How to Use the NAG Library and its Documentation for further information.
7
Accuracy
Eigenvalues and eigenvectors will normally be computed to the accuracy requested by the argument
tol, but eigenvectors corresponding to small or to close eigenvalues may not always be computed to the accuracy requested by the argument
tol. Use of the
monit to monitor acceptance of eigenvalues and eigenvectors is recommended.
8
Parallelism and Performance
f02fjf is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
f02fjf 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 routine. Please also consult the
Users' Note for your implementation for any additional implementationspecific information.
The time taken by
f02fjf will be principally determined by the time taken to solve the eigenvalue subproblem and the time taken by
dot and
image. The time taken to solve an eigenvalue subproblem is approximately proportional to
$n{k}^{2}$. 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=\lambda 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
${\stackrel{~}{d}}_{h}$, to the
$i$th eigenvalue, is accepted as soon as
${\stackrel{~}{d}}_{h}$ and the previous approximation differ by less than
$\left{\stackrel{~}{d}}_{h}\right\times {\mathbf{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
${d}_{r}$ is the last eigenvalue in such a group and we define the residual
${r}_{j}$ as
where
${y}_{r}$ is the projection of
$C{x}_{j}$, with respect to
$B$, onto the space spanned by
${x}_{1},{x}_{2},\dots ,{x}_{r}$, and
${x}_{j}$ is the current approximation to the
$j$th eigenvector, then the value
${f}_{i}$ returned in
monit is given by
and each vector in the group is accepted as an eigenvector if
where
$e$ is the current approximation to
$\left{\stackrel{~}{d}}_{k}\right$. The values of the
${f}_{i}$ 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 subproblem is solved using the singular value decomposition of the upper triangular matrix
$R$ of the Gram–Schmidt factorization of
$C{x}_{r}$, rather than forming
${R}^{\mathrm{T}}R$.
10
Example
This example finds the four eigenvalues of smallest absolute value and corresponding eigenvectors for the generalized symmetric eigenvalue problem
$Ax=\lambda Bx$, where
$A$ and
$B$ are the
$16$ by
$16$ matrices
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$.
Output from
monit occurs each time
istate is nonzero. Note that the required eigenvalues are the reciprocals of the eigenvalues returned by
f02fjf.
10.1
Program Text
Program Text (f02fjfe.f90)
10.2
Program Data
Program Data (f02fjfe.d)
10.3
Program Results
Program Results (f02fjfe.r)