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

naginterfaces.library.eigen.real_gen_sparse_arnoldi(a, icolzp, irowix, nev, ncv, sigma, monit=None, option=None, data=None, io_manager=None)

real_gen_sparse_arnoldi computes selected eigenvalues and eigenvectors of a real sparse general matrix.

Note: this function uses optional algorithmic parameters, see also: sparseig.real_init, sparseig.real_iter, sparseig.real_proc, sparseig.real_option, sparseig.real_monit.

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

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

Parameters

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

The array of nonzero elements (and diagonal elements if a nonzero inverse shift is to be applied) of the $n\times n$ general matrix $A$.

icolzpint, array-like, shape $(n+1)$

$icolzp[i-1]$ contains the index in $a$ of the start of column $\text{i}$, for $\text{i}=1,2,\dots ,n$; $icolzp\left[n\right]$ must contain the value $\text{nnz}+1$. Thus the number of nonzero elements in column $\text{i}$ of $A$ is $icolzp\left[i\right]-icolzp[i-1]$; when shifts are applied this includes diagonal elements irrespective of value. See the F11 Introduction.

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

$irowix[i-1]$ contains the row index for each entry in $a$. See the F11 Introduction.

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 CPU time is problem dependent and must be determined empirically.

sigmafloat

If the ‘Shifted Inverse Real’ 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_gen_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_gen_sparse_arnoldi.

Parameters

niterint

The number of the current Arnoldi iteration.

nconvint

The number of converged eigenvalues so far.

wcomplex, 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_option from within $option$. (Please note that it is only necessary to call sparseig.real_option; no call to sparseig.real_init is required from within $option$.) For example, you can set the mode to ‘Shifted Inverse Real’, 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_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

afloat, ndarray, shape $\left(\text{nnz}\right)$

If a nonzero shifted inverse is to be applied then the diagonal elements of $A$ have the shift value, as supplied in $sigma$, subtracted.

nconvint

The number of converged approximations to the selected eigenvalues. On successful exit, this will normally be either $nev$ or $nev+1$ depending on the number of complex conjugate pairs of eigenvalues returned.

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

The first $nconv$ elements contain the converged approximations to the selected eigenvalues. Since complex conjugate pairs of eigenvalues appear together, it is possible (given an odd number of converged real eigenvalues) for real_gen_sparse_arnoldi to return one more eigenvalue than requested.

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 a real eigenvalue, ${\lambda }_j$, the corresponding eigenvector is real and is stored in $v[\text{i}-1,j-1]$, for $\text{i}=1,2,\dots ,n$. For complex conjugate pairs of eigenvalues, $w_{j+1}=\overline{w_j}$, the real and imaginary parts of the corresponding eigenvectors are stored, respectively, in $v[\text{i}-1,j-1]$ and $v[\text{i}-1,j]$, for $\text{i}=1,2,\dots ,n$. The imaginary parts stored are for the first of the conjugate pair of eigenvectors; the other eigenvector in the pair is obtained by negating these imaginary parts.

residfloat, ndarray, shape $(nev+1)$

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 $=0$

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 Arnoldi iterations that can be performed before real_gen_sparse_arnoldi exits with $errno$ = 24.

‘Largest Magnitude’valueless

Default

The Arnoldi iterative method converges on a number of eigenvalues with given properties. The default is to compute the eigenvalues of largest magnitude using ‘Largest Magnitude’. Alternatively, eigenvalues may be chosen which have ‘Largest Real’ part, ‘Largest Imaginary’ part, ‘Smallest Magnitude’, ‘Smallest Real’ part or ‘Smallest Imaginary’ part.

Note that these options select the eigenvalue properties for eigenvalues of $op$ the linear operator determined by the computational mode and problem type.

‘Largest Imaginary’valueless

The Arnoldi iterative method converges on a number of eigenvalues with given properties. The default is to compute the eigenvalues of largest magnitude using ‘Largest Magnitude’. Alternatively, eigenvalues may be chosen which have ‘Largest Real’ part, ‘Largest Imaginary’ part, ‘Smallest Magnitude’, ‘Smallest Real’ part or ‘Smallest Imaginary’ part.

Note that these options select the eigenvalue properties for eigenvalues of $op$ the linear operator determined by the computational mode and problem type.

‘Largest Real’valueless

The Arnoldi iterative method converges on a number of eigenvalues with given properties. The default is to compute the eigenvalues of largest magnitude using ‘Largest Magnitude’. Alternatively, eigenvalues may be chosen which have ‘Largest Real’ part, ‘Largest Imaginary’ part, ‘Smallest Magnitude’, ‘Smallest Real’ part or ‘Smallest Imaginary’ part.

Note that these options select the eigenvalue properties for eigenvalues of $op$ the linear operator determined by the computational mode and problem type.

‘Smallest Imaginary’valueless

The Arnoldi iterative method converges on a number of eigenvalues with given properties. The default is to compute the eigenvalues of largest magnitude using ‘Largest Magnitude’. Alternatively, eigenvalues may be chosen which have ‘Largest Real’ part, ‘Largest Imaginary’ part, ‘Smallest Magnitude’, ‘Smallest Real’ part or ‘Smallest Imaginary’ part.

Note that these options select the eigenvalue properties for eigenvalues of $op$ the linear operator determined by the computational mode and problem type.

‘Smallest Magnitude’valueless

The Arnoldi iterative method converges on a number of eigenvalues with given properties. The default is to compute the eigenvalues of largest magnitude using ‘Largest Magnitude’. Alternatively, eigenvalues may be chosen which have ‘Largest Real’ part, ‘Largest Imaginary’ part, ‘Smallest Magnitude’, ‘Smallest Real’ part or ‘Smallest Imaginary’ part.

Note that these options select the eigenvalue properties for eigenvalues of $op$ the linear operator determined by the computational mode and problem type.

‘Smallest Real’valueless

The Arnoldi iterative method converges on a number of eigenvalues with given properties. The default is to compute the eigenvalues of largest magnitude using ‘Largest Magnitude’. Alternatively, eigenvalues may be chosen which have ‘Largest Real’ part, ‘Largest Imaginary’ part, ‘Smallest Magnitude’, ‘Smallest Real’ part or ‘Smallest Imaginary’ part.

Note that these options select the eigenvalue properties for eigenvalues of $op$ the linear operator determined by the computational mode and problem type.

‘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_gen_sparse_arnoldi as follows.

$i$	Output
$=0$	No output except error messages.
$>0$	The set of selected options.
$=2$	Problem and timing statistics when all calls to sparseig.real_iter have been completed.
$\ge 5$	A single line of summary output at each Arnoldi iteration.
$\ge 10$	If $\text{‘Monitoring'}>0$, then at each iteration, the length and additional steps of the current Arnoldi factorization and the number of converged Ritz values; during re-orthogonalization, the norm of initial/restarted starting vector.
$\ge 20$	Problem and timing statistics on final exit from sparseig.real_iter. If $\text{‘Monitoring'}>0$, then at each iteration, the number of shifts being applied, the eigenvalues and estimates of the Hessenberg matrix $H$, the size of the Arnoldi 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$, 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 compressed upper Hessenberg matrix $H$; during re-orthogonalization, the initial/restarted starting vector; during the Arnoldi iteration loop, a restart is flagged and the number of the residual requiring iterative refinement; while applying shifts, the indices of the shifts being applied.
$\ge 40$	If $\text{‘Monitoring'}>0$, then during the Arnoldi iteration loop, the Arnoldi 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 $\text{‘Monitoring'}>0$, then during Arnoldi iteration loop: norms of key components and the active column of $H$, norms of residuals during iterative refinement, the final upper Hessenberg matrix $H$; while applying shifts: number of shifts, shift values, block indices, updated matrix $H$; while computing eigenvalues of $H$: the matrix $H$, the computed eigenvalues and Ritz estimates.

‘Regular’valueless

Default

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

Given a standard eigenvalue problem in the form $Ax=\lambda x$ then the following modes are available with the appropriate operator $op\left(x\right)$.

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

‘Shifted Inverse Real’valueless

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

Given a standard eigenvalue problem in the form $Ax=\lambda x$ then the following modes are available with the appropriate operator $op\left(x\right)$.

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

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

(errno $3$)

On entry, in shifted inverse mode, the $j$th diagonal element of $A$ is not defined, for $j=⟨value⟩$.

(errno $4$)

On entry, $icolzp\left[0\right]=⟨value⟩$.

Constraint: $icolzp\left[0\right]=1$.

(errno $4$)

On entry, for $i=⟨value⟩$, $icolzp[i-1]=⟨value⟩$ and $icolzp\left[i\right]=⟨value⟩$.

Constraint: $icolzp[i-1]<icolzp\left[i\right]$.

(errno $4$)

On entry, $icolzp\left[n\right]=⟨value⟩$ and $\text{nnz}=⟨value⟩$.

Constraint: $icolzp\left[n\right]=\text{nnz}+1$.

(errno $5$)

On entry, in specification of column $⟨value⟩$, and for $j=⟨value⟩$, $irowix[j-1]=⟨value⟩$ and $irowix\left[j\right]=⟨value⟩$.

Constraint: $irowix[j-1]<irowix\left[j\right]$.

(errno $6$)

On entry, $nev=⟨value⟩$.

Constraint: $nev>0$.

(errno $7$)

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

Constraint: $ncv>nev+1$.

(errno $7$)

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

Constraint: $ncv\le n$.

(errno $8$)

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

(errno $8$)

On entry, the matrix $A-\sigma \times I$ is nearly numerically singular and could not be inverted. Try perturbing the value of $\sigma$. Norm of matrix $=⟨value⟩$, Reciprocal condition number $=⟨value⟩$.

(errno $21$)

The maximum number of iterations $\le 0$, the option ‘Iteration Limit’ has been set to $⟨value⟩$.

(errno $22$)

An unexpected internal error occurred when solving an eigenproblem.

This error should not occur. Please contact NAG.

(errno $23$)

An unexpected internal error occurred when solving an eigenproblem.

This error should not occur. Please contact NAG.

(errno $24$)

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 $25$)

No shifts could be applied during a cycle of the implicitly restarted Arnoldi iteration.

(errno $26$)

Could not build an Arnoldi factorization. The size of the current Arnoldi factorization $=⟨value⟩$.

(errno $27$)

Error in internal call to compute eigenvalues and corresponding error bounds of the current upper Hessenberg matrix.

Please contact NAG.

(errno $32$)

An unexpected internal error occurred when postprocessing an eigenproblem.

This error should not occur. Please contact NAG.

(errno $33$)

The number of eigenvalues found to sufficient accuracy is zero.

(errno $34$)

Internal inconsistency in the number of converged Ritz values. Number counted $=⟨value⟩$, number expected $=⟨value⟩$.

(errno $35$)

During calculation of a real Schur form, there was a failure to compute $⟨value⟩$ eigenvalues in a total of $⟨value⟩$ iterations.

(errno $36$)

The computed Schur form could not be reordered by an internal call.

This routine returned with $\text{errno}=⟨value⟩$.

Please contact NAG.

(errno $37$)

In calculating eigenvectors, an internal call returned with an error.

Please contact NAG.

Warns

NagCallbackTerminateWarning

(errno $9$)

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

(errno $10$)

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

Notes

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

$$A{w}_i={\lambda }_i{w}_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 real part, or, largest or smallest imaginary part. 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 real value are required then the shifted inverses of largest magnitude should be selected with shift equal to the required real value.

Note that even though $A$ is real, ${\lambda }_i$ and $w_i$ may be complex. If $w_i$ is an eigenvector corresponding to a complex eigenvalue ${\lambda }_i$, then the complex conjugate vector ${\overline{w}}_i$ is the eigenvector corresponding to the complex conjugate eigenvalue ${\overline{\lambda }}_i$. The eigenvalues in a complex conjugate pair ${\lambda }_i$ and ${\overline{\lambda }}_i$ are either both selected or both not selected.

The sparse matrix $A$ is stored in compressed column storage (CCS) format. See the F11 Introduction.

real_gen_sparse_arnoldi uses an implicitly restarted Arnoldi 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; further information on the solver used is provided in the F11 Introduction.

References

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

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