NAG Library Function Document
nag_eigen_real_symm_sparse_arnoldi (f02fkc)
Note: this function uses optional parameters to define choices in the problem specification. If you wish to use default
settings for all of the optional parameters, you need only read Sections 1 to 10 of this document. If, however, you wish to reset some or all of the settings this must be done by calling the option setting function nag_real_symm_sparse_eigensystem_option (f12fdc) from the user-supplied function option. Please refer to Section 11 for a detailed description of the specification of the optional parameters.
1
Purpose
nag_eigen_real_symm_sparse_arnoldi (f02fkc) computes selected eigenvalues and eigenvectors of a real sparse symmetric matrix.
2
Specification
#include <nag.h> |
#include <nagf02.h> |
void |
nag_eigen_real_symm_sparse_arnoldi (Integer n,
Integer nnz,
const double a[],
const Integer irow[],
const Integer icol[],
Integer nev,
Integer ncv,
double sigma,
Integer *nconv,
double w[],
double v[],
Integer pdv,
double resid[],
Nag_Comm *comm,
NagError *fail) |
|
3
Description
nag_eigen_real_symm_sparse_arnoldi (f02fkc) computes selected eigenvalues and the corresponding right eigenvectors of a real sparse symmetric matrix
:
A specified number, , of eigenvalues , or the shifted inverses , 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 (). 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
is stored in symmetric coordinate storage (SCS) format. See
Section 2.1.2 in the f11 Chapter Introduction.
nag_eigen_real_symm_sparse_arnoldi (f02fkc) 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
Section 9 while a fuller discussion is provided in the
f12 Chapter Introduction. If shifts are to be performed then operations using shifted inverse matrices are performed using a direct sparse solver.
4
References
Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore
HSL (2011) 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, Philidelphia
5
Arguments
- 1:
– IntegerInput
-
On entry: , the order of the matrix .
Constraint:
.
- 2:
– IntegerInput
-
On entry: the dimension of the array
a.The number of nonzero elements in the lower triangular part of the matrix
.
Constraint:
.
- 3:
– const doubleInput
-
On entry: the array of nonzero elements of the lower triangular part of the by symmetric matrix .
- 4:
– const IntegerInput
- 5:
– const IntegerInput
-
On entry: the row and column indices of the elements supplied in array
a.
If
and
then
is stored in
.
irow does not need to be ordered: an internal sort will force the correct ordering.
Constraint:
irow and
icol must satisfy these constraints:
and
, for
.
- 6:
– IntegerInput
-
On entry: the number of eigenvalues to be computed.
Constraint:
.
- 7:
– IntegerInput
-
On entry: the dimension of the array
w.
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
. 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.
Constraint:
.
- 8:
– doubleInput
-
On entry: if the
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.
- 9:
– function, supplied by the userExternal Function
-
monit is used to monitor the progress of
nag_eigen_real_symm_sparse_arnoldi (f02fkc).
monit may be specified as
NULLFN if no monitoring is actually required.
monit is called after the solution of each eigenvalue sub-problem and also just prior to return from
nag_eigen_real_symm_sparse_arnoldi (f02fkc).
The specification of
monit is:
- 1:
– IntegerInput
-
On entry: the dimension of the arrays
w and
rzest. The number of Arnoldi basis vectors used during the computation.
- 2:
– IntegerInput
-
On entry: the number of the current Arnoldi iteration.
- 3:
– IntegerInput
-
On entry: the number of converged eigenvalues so far.
- 4:
– const doubleInput
-
On entry: the first
nconv elements of
w contain the converged approximate eigenvalues.
- 5:
– const doubleInput
-
On entry: the first
nconv elements of
rzest contain the Ritz estimates (error bounds) on the converged approximate eigenvalues.
- 6:
– Integer *Input/Output
-
On entry: set to zero.
On exit: if set to a nonzero value
nag_eigen_real_symm_sparse_arnoldi (f02fkc) returns immediately with
NE_USER_STOP.
- 7:
– Nag_Comm *
Pointer to structure of type Nag_Comm; the following members are relevant to
monit.
- user – double *
- iuser – Integer *
- p – Pointer
The type Pointer will be
void *. Before calling
nag_eigen_real_symm_sparse_arnoldi (f02fkc) you may allocate memory and initialize these pointers with various quantities for use by
monit when called from
nag_eigen_real_symm_sparse_arnoldi (f02fkc) (see
Section 3.3.1.1 in How to Use the NAG Library and its Documentation).
- 10:
– function, supplied by the userExternal Function
-
You can supply non-default options to the Arnoldi eigensolver by repeated calls to
nag_real_symm_sparse_eigensystem_option (f12fdc) from within
option. (Please note that it is only necessary to call
nag_real_symm_sparse_eigensystem_option (f12fdc); no call to
nag_real_symm_sparse_eigensystem_init (f12fac) is required from within
option.) For example, you can set the mode to
, you can increase the
beyond its default and you can print varying levels of detail on the iterative process using
.
If only the default options (including that the eigenvalues of largest magnitude are sought) are to be used then
option may be specified as
NULLFN. See
Section 10 for an example of using
option to set some non-default options.
The specification of
option is:
- 1:
– IntegerCommunication Array
-
On entry: contains details of the default option set. This array must be passed as argument
icomm in any call to
nag_real_symm_sparse_eigensystem_option (f12fdc).
On exit: contains data on the current options set which may be altered from the default set via calls to
nag_real_symm_sparse_eigensystem_option (f12fdc).
- 2:
– doubleCommunication Array
-
On entry: contains details of the default option set. This array must be passed as argument
comm in any call to
nag_real_symm_sparse_eigensystem_option (f12fdc).
On exit: contains data on the current options set which may be altered from the default set via calls to
nag_real_symm_sparse_eigensystem_option (f12fdc).
- 3:
– Integer *Input/Output
-
On entry: set to zero.
On exit: if set to a nonzero value
nag_eigen_real_symm_sparse_arnoldi (f02fkc) returns immediately with
NE_USER_STOP.
- 4:
– Nag_Comm *
Pointer to structure of type Nag_Comm; the following members are relevant to
option.
- user – double *
- iuser – Integer *
- p – Pointer
The type Pointer will be
void *. Before calling
nag_eigen_real_symm_sparse_arnoldi (f02fkc) you may allocate memory and initialize these pointers with various quantities for use by
option when called from
nag_eigen_real_symm_sparse_arnoldi (f02fkc) (see
Section 3.3.1.1 in How to Use the NAG Library and its Documentation).
- 11:
– Integer *Output
-
On exit: the number of converged approximations to the selected eigenvalues. On successful exit, this will normally be
nev.
- 12:
– doubleOutput
-
On exit: the first
nconv elements contain the converged approximations to the selected eigenvalues.
- 13:
– doubleOutput
-
Note: the dimension,
dim, of the array
v
must be at least
.
On exit: contains the eigenvectors associated with the eigenvalue
, for
(stored in
w). For eigenvalue,
, the corresponding eigenvector is stored in
, for
.
- 14:
– IntegerInput
-
On entry: the stride separating, in the array
v, the elements of a real eigenvector from the corresponding elements of the next eigenvector.
Constraint:
.
- 15:
– doubleOutput
-
On exit: the residual for the estimates to the eigenpair and is returned in , for .
- 16:
– Nag_Comm *
-
The NAG communication argument (see
Section 3.3.1.1 in How to Use the NAG Library and its Documentation).
- 17:
– NagError *Input/Output
-
The NAG error argument (see
Section 3.7 in How to Use the NAG Library and its Documentation).
6
Error Indicators and Warnings
- NE_ALLOC_FAIL
-
Dynamic memory allocation failed.
See
Section 2.3.1.2 in How to Use the NAG Library and its Documentation for further information.
- NE_BAD_PARAM
-
On entry, argument had an illegal value.
- NE_BOTH_ENDS_1
-
The option has been set but only eigenvalue is requested.
- NE_INT
-
On entry, .
Constraint: .
On entry, .
Constraint: .
On entry, .
Constraint: .
- NE_INT_2
-
On entry, and .
Constraint: .
On entry, and .
Constraint: .
On entry, and .
Constraint: .
On entry, and .
Constraint: .
On entry, and .
Constraint: .
- NE_INTERNAL_ERROR
-
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact
NAG for assistance.
See
Section 2.7.6 in How to Use the NAG Library and its Documentation for further information.
A serious error, code
, has occurred in an internal call. Check all function calls and array sizes. If the call is correct then please contact
NAG for assistance.
- NE_INVALID_OPTION
-
The maximum number of iterations, through the optional parameter , has been set to a non-positive value.
- NE_NO_LICENCE
-
Your licence key may have expired or may not have been installed correctly.
See
Section 2.7.5 in How to Use the NAG Library and its Documentation for further information.
- NE_SINGULAR
-
On entry, the matrix is numerically singular and could not be inverted. Try perturbing the value of .
- NE_SPARSE_COL
-
On entry, for , , .
Constraint: .
- NE_SPARSE_ROW
-
On entry, for , .
Constraint: .
- NE_TOO_MANY_ITER
-
The maximum number of iterations has been reached.
The maximum number of iterations .
The number of converged eigenvalues .
See the function document for further details.
- NE_USER_STOP
-
User requested termination in
monit,
.
User requested termination in
option,
.
7
Accuracy
The relative accuracy of a Ritz value (eigenvalue approximation),
, is considered acceptable if its Ritz estimate
. The default value for
is the
machine precision given by
nag_machine_precision (X02AJC). The Ritz estimates are available via the
monit function at each iteration in the Arnoldi process, or can be printed by setting option
to a positive value.
8
Parallelism and Performance
nag_eigen_real_symm_sparse_arnoldi (f02fkc) is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
nag_eigen_real_symm_sparse_arnoldi (f02fkc) 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 function. Please also consult the
Users' Note for your implementation for any additional implementation-specific information.
nag_eigen_real_symm_sparse_arnoldi (f02fkc) calls functions based on the ARPACK suite in
Chapter f12. These functions use an implicitly restarted Lanczos iterative method to converge to approximations to a set of required eigenvalues (see the
f12 Chapter Introduction).
In the default
mode, only matrix-vector multiplications are performed using the sparse matrix
during the Lanczos process;
nag_sparse_sym_matvec (f11xec) can be used to perform this task. Each iteration is therefore cheap computationally, relative to the alternative,
, mode described below. It is most efficient (i.e., the total number of iterations required is small) when the eigenvalues of largest magnitude are sought and these are distinct.
Although there is an option for returning the smallest eigenvalues using this mode (see option), the number of iterations required for convergence will be far greater or the method may not converge at all. However, where convergence is achieved, mode may still prove to be the most efficient since no inversions are required. Where smallest eigenvalues are sought and mode is not suitable, or eigenvalues close to a given real value are sought, the mode should be used.
If the
mode is used (via a call to
nag_real_symm_sparse_eigensystem_option (f12fdc) in
option) then the matrix
is used in linear system solves by the Lanczos process. This is first factorized internally using a direct sparse
factorization under the assumption that the matrix is indefinite. If the factorization determines that the matrix is numerically singular then the function exits with an error. In this situation it is normally sufficient to perturb
by a small amount and call
nag_eigen_real_symm_sparse_arnoldi (f02fkc) again. After successful factorization, subsequent solves are performed by backsubstitution using the sparse factorization.
Finally, nag_eigen_real_symm_sparse_arnoldi (f02fkc) transforms the eigenvectors. Each eigenvector is normalized so that .
The monitoring function
monit provides some basic information on the convergence of the Lanczos iterations. Much greater levels of detail on the Lanczos process are available via option
. If this is set to a positive value then information will be printed, by default, to standard output. The destination of monitoring information can be changed using the
option.
9.1
Additional Licensor
The direct sparse factorization is performed by an implementation of HSL_MA97 (see
HSL (2011)).
10
Example
This example solves in mode, where is obtained from the standard central difference discretization of the one-dimensional Laplacian operator on , with zero Dirichlet boundary conditions.
10.1
Program Text
Program Text (f02fkce.c)
10.2
Program Data
Program Data (f02fkce.d)
10.3
Program Results
Program Results (f02fkce.r)
11
Optional Parameters
Internally
nag_eigen_real_symm_sparse_arnoldi (f02fkc) calls functions from the suite
nag_real_symm_sparse_eigensystem_init (f12fac),
nag_real_symm_sparse_eigensystem_iter (f12fbc),
nag_real_symm_sparse_eigensystem_sol (f12fcc),
nag_real_symm_sparse_eigensystem_option (f12fdc) and
nag_real_symm_sparse_eigensystem_monit (f12fec). Several optional parameters for these computational functions define choices in the problem specification or the algorithm logic. In order to reduce the number of formal arguments of
nag_eigen_real_symm_sparse_arnoldi (f02fkc) these optional parameters are also used here and have associated
default values that are usually appropriate. Therefore, you need only specify those optional parameters whose values are to be different from their default values.
Optional parameters may be specified via the user-supplied function
option in the call to
nag_eigen_real_symm_sparse_arnoldi (f02fkc).
option must be coded such that one call to
nag_real_symm_sparse_eigensystem_option (f12fdc) is necessary to set each optional parameter. All optional parameters you do not specify are set to their default values.
The remainder of this section can be skipped if you wish to use the default values for all optional parameters.
The following is a list of the optional parameters available. A full description of each optional parameter is provided in
Section 11.1.
11.1
Description of the Optional Parameters
For each option, we give a summary line, a description of the optional parameter and details of constraints.
The summary line contains:
- the keywords, where the minimum abbreviation of each keyword is underlined;
- a parameter value,
where the letters , and denote options that take character, integer and real values respectively;
- the default value, where the symbol is a generic notation for machine precision (see nag_machine_precision (X02AJC)).
Keywords and character values are case and white space insensitive.
Optional parameters used to specify files (e.g.,
and
) have type Integer. This Integer value corresponds with the Nag_FileID as returned by
nag_open_file (x04acc). See
Section 10 for an example of the use of this facility.
(See
Section 3.3.1.1 in How to Use the NAG Library and its Documentation for further information on NAG data types.)
If the optional parameter
is set then optional parameter specifications are listed in a
file by setting the option to a file identification (unit) number associated with
messages (see
nag_open_file (x04acc)).
This special keyword may be used to reset all optional parameters to their default values.
Iteration Limit | |
Default |
The limit on the number of Lanczos iterations that can be performed before
nag_real_symm_sparse_eigensystem_iter (f12fbc) exits. If not all requested eigenvalues have converged to within
and the number of Lanczos iterations has reached this limit then
nag_real_symm_sparse_eigensystem_iter (f12fbc) exits with an error;
nag_real_symm_sparse_eigensystem_sol (f12fcc) can still be called subsequently to return the number of converged eigenvalues, the converged eigenvalues and, if requested, the corresponding eigenvectors.
Largest Magnitude | | Default |
The Lanczos iterative method converges on a number of eigenvalues with given properties. The default is for
nag_real_symm_sparse_eigensystem_iter (f12fbc) to compute the eigenvalues of largest magnitude using
. Alternatively, eigenvalues may be chosen which have
part,
, or
part; or eigenvalues which are from
of the algebraic spectrum.
Normally each optional parameter specification is not listed as it is supplied. This behaviour can be changed using the and options.
(See
Section 3.3.1.1 in How to Use the NAG Library and its Documentation for further information on NAG data types.)
Unless
is set to
(the default), monitoring information is output to Nag_FileID
during the solution of each problem; this may be the same as
. The type of information produced is dependent on the value of
, see the description of the optional parameter
in this section for details of the information produced. Please see
nag_open_file (x04acc) to associate a file with a given Nag_FileID.
This controls the amount of printing produced by
nag_eigen_real_symm_sparse_arnoldi (f02fkc) as follows.
|
No output except error messages. If you want to suppress all output, set . |
|
The set of selected options. |
|
Problem and timing statistics on final exit from nag_real_symm_sparse_eigensystem_iter (f12fbc). |
|
A single line of summary output at each Lanczos iteration. |
|
If
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. |
|
Problem and timing statistics on final exit from nag_real_symm_sparse_eigensystem_iter (f12fbc). If
is set,
then at each iteration, the number of shifts being applied, the eigenvalues and estimates of the symmetric tridiagonal matrix , 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. |
|
If
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 ; 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. |
|
If
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 ; while computing eigenvalues of , the last rows of the Schur and eigenvector matrices; when computing implicit shifts, the eigenvalues and Ritz estimates of . |
|
If is set, then during Lanczos iteration loop: norms of key components and the active column of , norms of residuals during iterative refinement, the final symmetric tridiagonal matrix ; while applying shifts: number of shifts, shift values, block indices, updated tridiagonal matrix ; while computing eigenvalues of : the diagonals of , the computed eigenvalues and Ritz estimates. |
Note that setting can result in very lengthy output.
These options define the computational mode which in turn defines the form of operation to be performed.
|
|
|
where is real |
|
|
An approximate eigenvalue has deemed to have converged when the corresponding Ritz estimate is within relative to the magnitude of the eigenvalue.