naginterfaces.library.eigen.real_​symm_​sparse_​eigsys

naginterfaces.library.eigen.real_symm_sparse_eigsys(m, noits, tol, dot, image, novecs, x, monit=None, data=None)

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

For full information please refer to the NAG Library document for f02fj

https://support.nag.com/numeric/nl/nagdoc_30.1/flhtml/f02/f02fjf.html

Parameters

mint

$m$, the number of eigenvalues required.

noitsint

The maximum number of major iterations (eigenvalue sub-problems) to be performed. If $noits\le 0$, the value $100$ is used in place of $noits$.

tolfloat

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|{\tilde{d}}_i\right|\times tol)/10$, where ${\tilde{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)/(d_i-d_k)<tol$, where $f_i$ is the normalized residual of the current approximation to the eigenvector (see Further Comments for further information). The values of the $f_i$ and $d_i$ 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$.

dotcallable retval = dot(z, w, data=None)

$dot$ must return the value $w^{T}Bz$ for given vectors $w$ and $z$.

For the standard eigenvalue problem, where $B=I$, $dot$ must return the dot product $w^{T}z$.

Parameters

zfloat, ndarray, shape $\left(n\right)$

The vector $z$ for which $w^{T}Bz$ is required.

wfloat, ndarray, shape $\left(n\right)$

The vector $w$ for which $w^{T}Bz$ is required.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

Returns

retvalfloat

The value $w^{T}Bz$.

imagecallable w = image(z, data=None)

$image$ must return the vector $w=Cz$ for a given vector $z$.

Parameters

zfloat, ndarray, shape $\left(n\right)$

The vector $z$ for which $Cz$ is required.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

Returns

wfloat, array-like, shape $\left(n\right)$

The vector $w=Cz$.

novecsint

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$.

xfloat, array-like, shape $(n,k)$

If $0<novecs\le 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 real_symm_sparse_eigsys is being restarted with a larger value of $\text{k}$. Otherwise it is not necessary to supply approximate vectors, as simultaneous iteration vectors will be generated randomly by real_symm_sparse_eigsys.

monitNone or callable monit(istate, nextit, nevals, nevecs, f, d, data=None), optional

Note: if this argument is None then a NAG-supplied facility will be used.

$monit$ is used to monitor the progress of real_symm_sparse_eigsys. $monit$ may be None if no monitoring is actually required. $monit$ is called after the solution of each eigenvalue sub-problem and also just prior to return from real_symm_sparse_eigsys.

The arguments $istate$ and $nextit$ allow selective printing by $monit$.

Parameters

istateint

Specifies the state of real_symm_sparse_eigsys.

$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 real_symm_sparse_eigsys is about to occur.

nextitint

The number of the next iteration.

nevalsint

The number of eigenvalues accepted so far.

nevecsint

The number of eigenvectors accepted so far.

ffloat, ndarray, shape $\left(k\right)$

A vector of error quantities measuring the state of convergence of the simultaneous iteration vectors. See $tol$ and Further Comments 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.

dfloat, ndarray, shape $\left(k\right)$

$d[i-1]$ contains the latest approximation to the absolute value of the $i$th eigenvalue of $C$.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

dataarbitrary, optional

User-communication data for callback functions.

Returns

mint

$m^{\prime }$, the number of eigenvalues actually found. It is equal to $m$ if no exception or warning is raised on exit, and is less than $m$ if $errno$ = 2, 3 or 4. See Exceptions and Further Comments for further information.

noitsint

The number of iterations actually performed.

xfloat, ndarray, shape $(n,k)$

If the function exits successfully or $errno$ = 2, 3 or 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.

dfloat, ndarray, shape $\left(k\right)$

If the function exits successfully or $errno$ = 2, 3 or 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. $d[k-1]$ contains the value $e$ where $(-e,e)$ is the latest interval over which Chebyshev acceleration is performed.

Raises

NagValueError

(errno $1$)

On entry, $k=⟨value⟩$ and $n=⟨value⟩$.

Constraint: $k\le n$.

(errno $1$)

On entry, $m=⟨value⟩$ and $k=⟨value⟩$.

Constraint: $m<k$.

(errno $1$)

On entry, $m=⟨value⟩$.

Constraint: $m\ge 1$.

(errno $1$)

On entry, $n=⟨value⟩$.

Constraint: $n\ge 1$.

(errno $5$)

Not all requested eigenvalues and vectors have been obtained.

(errno $5$)

Convergence of eigenvalue sub-problem occurred.

Warns

NagAlgorithmicWarning

(errno $2$)

Not all requested eigenvalues and vectors have been obtained.

(errno $3$)

Not all requested eigenvalues and vectors have been obtained.

(errno $4$)

Not all requested eigenvalues and vectors have been obtained.

NagCallbackTerminateWarning

(errno $i<0$)

User set $iflag$ negative in $dot$ or $image$.

Notes

No equivalent traditional C interface for this routine exists in the NAG Library.

real_symm_sparse_eigsys finds the $m$ eigenvalues of largest absolute value and the corresponding eigenvectors for the real eigenvalue problem

$$Cx=\lambda x$$

where $C$ is an $n\times n$ matrix such that

$$BC=C^{T}B$$

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\text{and}B=I\text{where}A=A^T$$

the function finds the $m$ eigenvalues of largest absolute magnitude for the standard symmetric eigenvalue problem

$$Ax=\lambda x\text{.}$$

The function is intended for the case where $A$ is sparse.

As a second example, when

$$C=B^{-1}A$$

where

$$A=A^T$$

the function finds the $m$ eigenvalues of largest absolute magnitude for the generalized symmetric eigenvalue problem

$$Ax=\lambda Bx\text{.}$$

The function is intended for the case where $A$ and $B$ are sparse.

The function 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\text{.}$$

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 [label omitted]. It should be remembered that the function 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.

[table omitted]

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^{T}Bz$.

real_symm_sparse_eigsys 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 function 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 real_symm_sparse_eigsys. 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 real_symm_sparse_eigsys may be re-entered, supplying approximations to the $k$ eigenvectors found so far and with $k$ then increased.

At each major iteration real_symm_sparse_eigsys solves an $r\times r$ ($r\le k$) 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.

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