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

naginterfaces.library.eigen.real_symm_sparse_arnoldi(n, a, irow, icol, nev, ncv, sigma, monit=None, option=None, data=None, io_manager=None)

real_symm_sparse_arnoldi computes selected eigenvalues and eigenvectors of a real sparse symmetric matrix.

Note: this function uses optional algorithmic parameters, see also: sparseig.real_symm_init, sparseig.real_symm_iter, sparseig.real_symm_proc, sparseig.real_symm_option, sparseig.real_symm_monit.

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

https://support.nag.com/numeric/nl/nagdoc_30.3/flhtml/f02/f02fkf.html

Parameters

nint

$n$, the order of the matrix $A$.

afloat, array-like, shape $\left(\text{nnz}\right)$

The array of nonzero elements of the lower triangular part of the $n\times n$ symmetric matrix $A$.

irowint, array-like, shape $\left(\text{nnz}\right)$

The row and column indices of the elements supplied in array $a$.

If $irow[k-1]=i$ and $icol[k-1]=j$ then $A_{ij}$ is stored in $a[k-1]$. $irow$ does not need to be ordered: an internal sort will force the correct ordering.

icolint, array-like, shape $\left(\text{nnz}\right)$

The row and column indices of the elements supplied in array $a$.

If $irow[k-1]=i$ and $icol[k-1]=j$ then $A_{ij}$ is stored in $a[k-1]$. $irow$ does not need to be ordered: an internal sort will force the correct ordering.

nevint

The number of eigenvalues to be computed.

ncvint

The number of Arnoldi basis vectors to use during the computation.

At present there is no a priori analysis to guide the selection of $ncv$ relative to $nev$.

However, it is recommended that $ncv\ge 2\times nev+1$.

If many problems of the same type are to be solved, you should experiment with increasing $ncv$ while keeping $nev$ fixed for a given test problem.

This will usually decrease the required number of matrix-vector operations but it also increases the work and storage required to maintain the orthogonal basis vectors.

The optimal ‘cross-over’ with respect to computation time is problem dependent and must be determined empirically.

sigmafloat

If the ‘Shifted Inverse’ mode has been selected then $sigma$ contains the real shift used; otherwise $sigma$ is not referenced. This mode can be selected by setting the appropriate options in the user-supplied function $option$.

monitNone or callable monit(niter, nconv, w, rzest, 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_arnoldi. $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_arnoldi.

Parameters

niterint

The number of the current Arnoldi iteration.

nconvint

The number of converged eigenvalues so far.

wfloat, ndarray, shape $\left(\text{ncv}\right)$

The first $nconv$ elements of $w$ contain the converged approximate eigenvalues.

rzestfloat, ndarray, shape $\left(\text{ncv}\right)$

The first $nconv$ elements of $rzest$ contain the Ritz estimates (error bounds) on the converged approximate eigenvalues.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

optionNone or callable option(comm, data=None), optional

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

You can supply non-default options to the Arnoldi eigensolver by repeated calls to sparseig.real_symm_option from within $option$. (Please note that it is only necessary to call sparseig.real_symm_option; no call to sparseig.real_symm_init is required from within $option$.) For example, you can set the mode to ‘Shifted Inverse’, you can increase the ‘Iteration Limit’ beyond its default and you can print varying levels of detail on the iterative process using ‘Print Level’.

If only the default options (including that the eigenvalues of largest magnitude are sought) are to be used then $option$ may be None.

Parameters

commdict, communication object, modifiable in place

Communication structure.

This argument has been initialized to hold the default option set.

If you wish to supply non-default options to the Arnoldi eigensolver, this argument may be passed as argument $\text{comm}$ in a call to sparseig.real_symm_option.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

dataarbitrary, optional

User-communication data for callback functions.

io_managerFileObjManager, optional

Manager for I/O in this routine.

Returns

nconvint

The number of converged approximations to the selected eigenvalues. On successful exit, this will normally be $nev$.

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

The first $nconv$ elements contain the converged approximations to the selected eigenvalues.

vfloat, ndarray, shape $(n,ncv)$

Contains the eigenvectors associated with the eigenvalue ${\lambda }_{\text{i}}$, for $\text{i}=1,2,\dots ,nconv$ (stored in $w$). For eigenvalue, ${\lambda }_j$, the corresponding eigenvector is stored in $v[\text{i}-1,j-1]$, for $\text{i}=1,2,\dots ,n$.

residfloat, ndarray, shape $\left(nev\right)$

The residual ${\parallel A{w}_{\text{i}}-{\lambda }_{\text{i}}{w}_{\text{i}}\parallel }_2$ for the estimates to the eigenpair ${\lambda }_{\text{i}}$ and $w_{\text{i}}$ is returned in $resid[\text{i}-1]$, for $\text{i}=1,2,\dots ,nconv$.

Other Parameters

‘Advisory’int

Default $=\text{advisory message unit number}$

If the option ‘List’ is set then option specifications are listed in a ‘List’ file by setting the option to a file identification (unit) number associated with advisory messages (see FileObjManager and the FileObjManager method unit_from_fileobj()).

‘Defaults’valueless

This special keyword may be used to reset all options to their default values.

‘Iteration Limit’int

Default $=300$

The limit on the number of Lanczos iterations that can be performed before sparseig.real_symm_iter exits. If not all requested eigenvalues have converged to within ‘Tolerance’ and the number of Lanczos iterations has reached this limit then sparseig.real_symm_iter exits with an error; sparseig.real_symm_proc can still be called subsequently to return the number of converged eigenvalues, the converged eigenvalues and, if requested, the corresponding eigenvectors.

‘Largest Magnitude’valueless

Default

The Lanczos iterative method converges on a number of eigenvalues with given properties. The default is for sparseig.real_symm_iter to compute the eigenvalues of largest magnitude using ‘Largest Magnitude’. Alternatively, eigenvalues may be chosen which have ‘Largest Algebraic’ part, ‘Smallest Magnitude’, or ‘Smallest Algebraic’ part; or eigenvalues which are from ‘Both Ends’ of the algebraic spectrum.

‘Both Ends’valueless

The Lanczos iterative method converges on a number of eigenvalues with given properties. The default is for sparseig.real_symm_iter to compute the eigenvalues of largest magnitude using ‘Largest Magnitude’. Alternatively, eigenvalues may be chosen which have ‘Largest Algebraic’ part, ‘Smallest Magnitude’, or ‘Smallest Algebraic’ part; or eigenvalues which are from ‘Both Ends’ of the algebraic spectrum.

‘Largest Algebraic’valueless

The Lanczos iterative method converges on a number of eigenvalues with given properties. The default is for sparseig.real_symm_iter to compute the eigenvalues of largest magnitude using ‘Largest Magnitude’. Alternatively, eigenvalues may be chosen which have ‘Largest Algebraic’ part, ‘Smallest Magnitude’, or ‘Smallest Algebraic’ part; or eigenvalues which are from ‘Both Ends’ of the algebraic spectrum.

‘Smallest Algebraic’valueless

The Lanczos iterative method converges on a number of eigenvalues with given properties. The default is for sparseig.real_symm_iter to compute the eigenvalues of largest magnitude using ‘Largest Magnitude’. Alternatively, eigenvalues may be chosen which have ‘Largest Algebraic’ part, ‘Smallest Magnitude’, or ‘Smallest Algebraic’ part; or eigenvalues which are from ‘Both Ends’ of the algebraic spectrum.

‘Smallest Magnitude’valueless

The Lanczos iterative method converges on a number of eigenvalues with given properties. The default is for sparseig.real_symm_iter to compute the eigenvalues of largest magnitude using ‘Largest Magnitude’. Alternatively, eigenvalues may be chosen which have ‘Largest Algebraic’ part, ‘Smallest Magnitude’, or ‘Smallest Algebraic’ part; or eigenvalues which are from ‘Both Ends’ of the algebraic spectrum.

‘Nolist’valueless

Default

Option ‘List’ enables printing of each option specification as it is supplied. ‘Nolist’ suppresses this printing.

‘List’valueless

Option ‘List’ enables printing of each option specification as it is supplied. ‘Nolist’ suppresses this printing.

‘Monitoring’int

Default $=-1$

If $i>0$, monitoring information is output to unit number (see unit_from_fileobj()) $i$ during the solution of each problem; this may be the same as the ‘Advisory’ unit number (see unit_from_fileobj()). The type of information produced is dependent on the value of ‘Print Level’, see the description of the option ‘Print Level’ for details of the information produced. Please see the FileObjManager method unit_from_fileobj() to associate a file with a given unit number (see unit_from_fileobj()).

‘Print Level’int

Default $=0$

This controls the amount of printing produced by real_symm_sparse_arnoldi as follows.

$i$	Output
$=0$	No output except error messages. If you want to suppress all output, set $\text{‘Print Level'}=0$.
$>0$	The set of selected options.
$=2$	Problem and timing statistics on final exit from sparseig.real_symm_iter.
$\ge 5$	A single line of summary output at each Lanczos iteration.
$\ge 10$	If ‘Monitoring’ is set, then at each iteration, the length and additional steps of the current Lanczos factorization and the number of converged Ritz values; during re-orthogonalization, the norm of initial/restarted starting vector; on a final Lanczos iteration, the number of update iterations taken, the number of converged eigenvalues, the converged eigenvalues and their Ritz estimates.
$\ge 20$	Problem and timing statistics on final exit from sparseig.real_symm_iter. If $\text{‘Monitoring'}>0$, ‘Monitoring’ is set, then at each iteration, the number of shifts being applied, the eigenvalues and estimates of the symmetric tridiagonal matrix $H$, the size of the Lanczos basis, the wanted Ritz values and associated Ritz estimates and the shifts applied; vector norms prior to and following re-orthogonalization.
$\ge 30$	If $\text{‘Monitoring'}>0$, ‘Monitoring’ is set, then on final iteration, the norm of the residual; when computing the Schur form, the eigenvalues and Ritz estimates both before and after sorting; for each iteration, the norm of residual for compressed factorization and the symmetric tridiagonal matrix $H$; during re-orthogonalization, the initial/restarted starting vector; during the Lanczos iteration loop, a restart is flagged and the number of the residual requiring iterative refinement; while applying shifts, some indices.
$\ge 40$	If $\text{‘Monitoring'}>0$, ‘Monitoring’ is set, then during the Lanczos iteration loop, the Lanczos vector number and norm of the current residual; while applying shifts, key measures of progress and the order of $H$; while computing eigenvalues of $H$, the last rows of the Schur and eigenvector matrices; when computing implicit shifts, the eigenvalues and Ritz estimates of $H$.
$\ge 50$	If ‘Monitoring’ is set, then during Lanczos iteration loop: norms of key components and the active column of $H$, norms of residuals during iterative refinement, the final symmetric tridiagonal matrix $H$; while applying shifts: number of shifts, shift values, block indices, updated tridiagonal matrix $H$; while computing eigenvalues of $H$: the diagonals of $H$, the computed eigenvalues and Ritz estimates.

Note that setting $\text{‘Print Level'}\ge 30$ can result in very lengthy ‘Monitoring’ output.

‘Regular’valueless

Default

These options define the computational mode which in turn defines the form of operation $op\left(x\right)$ to be performed.

‘Regular’	$op=A$
‘Shifted Inverse’	$op={(A-\sigma I)}^{-1}$ where $\sigma$ is real
‘Regular Inverse’	$op=A^{-1}$

‘Regular Inverse’valueless

These options define the computational mode which in turn defines the form of operation $op\left(x\right)$ to be performed.

‘Regular’	$op=A$
‘Shifted Inverse’	$op={(A-\sigma I)}^{-1}$ where $\sigma$ is real
‘Regular Inverse’	$op=A^{-1}$

‘Shifted Inverse’valueless

These options define the computational mode which in turn defines the form of operation $op\left(x\right)$ to be performed.

‘Regular’	$op=A$
‘Shifted Inverse’	$op={(A-\sigma I)}^{-1}$ where $\sigma$ is real
‘Regular Inverse’	$op=A^{-1}$

‘Tolerance’float

Default $=ϵ$

An approximate eigenvalue has deemed to have converged when the corresponding Ritz estimate is within ‘Tolerance’ relative to the magnitude of the eigenvalue.

Raises

NagValueError

(errno $1$)

On entry, $n=⟨value⟩$.

Constraint: $n>0$.

(errno $2$)

On entry, $\text{nnz}=⟨value⟩$.

Constraint: $\text{nnz}>0$.

(errno $2$)

On entry, $\text{nnz}=⟨value⟩$ and $n=⟨value⟩$.

Constraint: $\text{nnz}\le n\times (n+1)/2$.

(errno $4$)

On entry, for $i=⟨value⟩$, $irow[i-1]=⟨value⟩$.

Constraint: $1\le irow[i-1]\le n$.

(errno $5$)

On entry, for $i=⟨value⟩$, $icol[i-1]=⟨value⟩$, $irow[i-1]=⟨value⟩$.

Constraint: $1\le icol[i-1]\le irow[i-1]$.

(errno $6$)

On entry, $nev=⟨value⟩$.

Constraint: $nev>0$.

(errno $6$)

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

Constraint: $nev<(n-1)$.

(errno $7$)

On entry, $ncv=⟨value⟩$ and $nev=⟨value⟩$.

Constraint: $ncv>nev$.

(errno $7$)

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

Constraint: $ncv\le n$.

(errno $8$)

On entry, the matrix $(A-\sigma I)$ is numerically singular and could not be inverted. Try perturbing the value of $\sigma$.

(errno $20$)

The maximum number of iterations, through the option ‘Iteration Limit’, has been set to a non-positive value.

(errno $21$)

The option ‘Both Ends’ has been set but only $1$ eigenvalue is requested.

(errno $22$)

The maximum number of iterations has been reached.

The maximum number of iterations $=⟨value⟩$.

The number of converged eigenvalues $=⟨value⟩$.

See the function document for further details.

(errno $30$)

A serious error, code $(⟨value⟩,⟨value⟩)$, has occurred in an internal call. Check all function calls and array sizes. If the call is correct then please contact NAG for assistance.

Warns

NagCallbackTerminateWarning

(errno $9$)

User requested termination in $monit$, $istat=⟨value⟩$.

(errno $10$)

User requested termination in $option$, $istat=⟨value⟩$.

Notes

real_symm_sparse_arnoldi computes selected eigenvalues and the corresponding right eigenvectors of a real sparse symmetric matrix $A$:

$$A{v}_i={\lambda }_i{v}_i\text{.}$$

A specified number, $n_{ev}$, of eigenvalues ${\lambda }_i$, or the shifted inverses ${\mu }_i=1/({\lambda }_i-\sigma )$, may be selected either by largest or smallest modulus, largest or smallest value, or, largest and smallest values (both ends). Convergence is generally faster when selecting larger eigenvalues, smaller eigenvalues can always be selected by choosing a zero inverse shift ($\sigma =0.0$). When eigenvalues closest to a given value are required then the shifted inverses of largest magnitude should be selected with shift equal to the required value.

The sparse matrix $A$ is stored in symmetric coordinate storage (SCS) format. See the F11 Introduction.

real_symm_sparse_arnoldi uses an implicitly restarted Arnoldi (Lanczos) iterative method to converge approximations to a set of required eigenvalues and corresponding eigenvectors. Further algorithmic information is given in Further Comments while a fuller discussion is provided in the F12 Introduction. If shifts are to be performed then operations using shifted inverse matrices are performed using a direct sparse solver.

References

Golub, G H and Van Loan, C F, 1996, Matrix Computations, (3rd Edition), Johns Hopkins University Press, Baltimore

HSL, a collection of Fortran codes for large-scale scientific computation, http://www.hsl.rl.ac.uk/

Lehoucq, R B, Sorensen, D C and Yang, C, 1998, ARPACK Users’ Guide: Solution of Large-scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods, SIAM, Philadelphia