arpack {igraph} | R Documentation

## ARPACK eigenvector calculation

### Description

Interface to the ARPACK library for calculating eigenvectors of sparse matrices

### Usage

    arpack(func, extra = NULL, sym = FALSE, options = igraph.arpack.default,
        env = parent.frame(), complex=!sym)
    arpack.unpack.complex(vectors, values, nev)

### Arguments

`func` | The function to perform the matrix-vector multiplication. ARPACK requires to perform these by the user. The function gets the vector x as the first argument, and it should return Ax, where A is the “input matrix”. (The input matrix is never given explicitly.) The second argument is `extra`.
`extra` | Extra argument to supply to `func`.
`sym` | Logical scalar, whether the input matrix is symmetric. Always supply `TRUE` here if it is, since it can speed up the computation.
`options` | Options to ARPACK, a named list to overwrite some of the default option values. See details below.
`env` | The environment in which `func` will be evaluated.
`complex` | Whether to convert the eigenvectors returned by ARPACK into R complex vectors. By default this is not done for symmetric problems (these only have real eigenvectors/values), but only non-symmetric ones. If you have a non-symmetric problem, but you're sure that the results will be real, then supply `FALSE` here. The conversion is done by calling `arpack.unpack.complex`.
`vectors` | Eigenvectors, as returned by ARPACK.
`values` | Eigenvalues, as returned by ARPACK
`nev` | The number of eigenvectors/values to extract. This can be less than or equal to the number of eigenvalues requested in the original ARPACK call.

### Details

ARPACK is a library for solving large scale eigenvalue problems. The package is designed to compute a few eigenvalues and corresponding eigenvectors of a general n by n matrix A. It is most appropriate for large sparse or structured matrices A where structured means that a matrix-vector product `w <- Av` requires order n rather than the usual order n^2 floating point operations. Please see http://www.caam.rice.edu/software/ARPACK/ for details.

This function is an interface to ARPACK. igraph does not contain all ARPACK routines, only the ones dealing with symmetric and non-symmetric eigenvalue problems using double precision real numbers.

The eigenvalue calculation in ARPACK (in the simplest case) involves the calculation of the Av product where A is the matrix we work with and v is an arbitrary vector. The function supplied in the `fun` argument is expected to perform this product. If the product can be done efficiently, e.g. if the matrix is sparse, then `arpack` is usually able to calculate the eigenvalues very quickly.

The `options` argument specifies what kind of calculation to perform. It is a list with the following members, they correspond directly to ARPACK parameters. On input it has the following fields:

bmat
  Character constant, possible values: ‘`I`’, stadard eigenvalue problem, A*x=lambda*x; and ‘`G`’, generalized eigenvalue problem, A*x=lambda B*x. Currently only ‘`I`’ is supported.
n
  Numeric scalar. The dimension of the eigenproblem. You only need to set this if you call `arpack` directly. (I.e. not needed for `evcent`, `page.rank`, etc.)
which
  Specify which eigenvalues/vectors to compute, character constant with exactly two characters.

  Possible values for symmetric input matrices:

‘`LA`’
  Compute `nev` largest (algebraic) eigenvalues.
‘`SA`’
  Compute `nev` smallest (algebraic) eigenvalues.
‘`LM`’
  Compute `nev` largest (in magnitude) eigenvalues.
‘`SM`’
  Compute `nev` smallest (in magnitude) eigenvalues.
‘`BE`’
  Compute `nev` eigenvalues, half from each end of the spectrum. When `nev` is odd, compute one more from the high end than from the low end.

Possible values for non-symmetric input matrices:

‘`LM`’
  Compute `nev` eigenvalues of largest magnitude.
‘`SM`’
  Compute `nev` eigenvalues of smallest magnitude.
‘`LR`’
  Compute `nev` eigenvalues of largest real part.
‘`SR`’
  Compute `nev` eigenvalues of smallest real part.
‘`LI`’
  Compute `nev` eigenvalues of largest imaginary part.
‘`SI`’
  Compute `nev` eigenvalues of smallest imaginary part.

This parameter is sometimes overwritten by the various functions, e.g. `page.rank` always sets ‘`LM`’.

nev
  Numeric scalar. The number of eigenvalues to be computed.
tol
  Numeric scalar. Stopping criterion: the relative accuracy of the Ritz value is considered acceptable if its error is less than `tol` times its estimated value. If this is set to zero then machine precision is used.
ncv
  Number of Lanczos vectors to be generated.
ldv
  Numberic scalar. It should be set to zero in the current implementation.
ishift
  Either zero or one. If zero then the shifts are provided by the user via reverse communication. If one then exact shifts with respect to the reduced tridiagonal matrix T. Please always set this to one.
maxiter
  Maximum number of Arnoldi update iterations allowed.
nb
  Blocksize to be used in the recurrence. Please always leave this on the default value, one.
mode
  The type of the eigenproblem to be solved. Possible values if the input matrix is symmetric:
1
  A*x=lambda*x, A is symmetric.
2
  A*x=lambda*M*x, A is symmetric, M is symmetric positive definite.
3
  K*x=lambda*M*x, K is symmetric, M is symmetric positive semi-definite.
4
  K*x=lambda*KG*x, K is symmetric positive semi-definite, KG is symmetric indefinite.
5
  A*x=lambda*M*x, A is symmetric, M is symmetric positive semi-definite. (Cayley transformed mode.)

Please note that only `mode==1` was tested and other values might not work properly.

Possible values if the input matrix is not symmetric:

1
  A*x=lambda*x.
2
  A*x=lambda*M*x, M is symmetric positive definite.
3
  A*x=lambda*M*x, M is symmetric semi-definite.
4
  A*x=lambda*M*x, M is symmetric semi-definite.

Please note that only `mode==1` was tested and other values might not work properly.

start
  Not used currently. Later it be used to set a starting vector.
sigma
  Not used currently.
sigmai
  Not use currently.

On output the following additional fields are added:

info
  Error flag of ARPACK. Possible values:
0
  Normal exit.
1
  Maximum number of iterations taken.
3
  No shifts could be applied during a cycle of the Implicitly restarted Arnoldi iteration. One possibility is to increase the size of `ncv` relative to `nev`.

ARPACK can return more error conditions than these, but they are converted to regular igraph errors.

iter
  Number of Arnoldi iterations taken.
nconv
  Number of “converged” Ritz values. This represents the number of Ritz values that satisfy the convergence critetion.
numop
  Total number of matrix-vector multiplications.
numopb
  Not used currently.
numreo
  Total number of steps of re-orthogonalization.

Please see the ARPACK documentation for additional details.

`arpack.unpack.complex` is a (semi-)internal function that converts the output of the non-symmetric ARPACK solver to a more readable format. It is called internally by `arpack`.

### Value

A named list with the following members:

`values` | Numeric vector, the desired eigenvalues.
`vectors` | Numeric matrix, the desired eigenvectors as columns. If `complex=TRUE` (the default for non-symmetric problems), then the matrix is complex.
`options` | A named list with the supplied `options` and some information about the performed calculation, including an ARPACK exit code. See the details above.

### Author(s)

Rich Lehoucq, Kristi Maschhoff, Danny Sorensen, Chao Yang for ARPACK, Gabor Csardi csardi@rmki.kfki.hu for the R interface.

### References

D.C. Sorensen, Implicit Application of Polynomial Filters in a k-Step Arnoldi Method. SIAM J. Matr. Anal. Apps., 13 (1992), pp 357-385.

R.B. Lehoucq, Analysis and Implementation of an Implicitly Restarted Arnoldi Iteration. Rice University Technical Report TR95-13, Department of Computational and Applied Mathematics.

B.N. Parlett & Y. Saad, Complex Shift and Invert Strategies for Real Matrices. Linear Algebra and its Applications, vol 88/89, pp 575-595, (1987).

### See Also

`evcent`, `page.rank`, `hub.score`, `leading.eigenvector.community` are some of the functions in igraph which use ARPACK. The ARPACK homepage is at http://www.caam.rice.edu/software/ARPACK/.

### Examples

    # Identity matrix
    f <- function(x, extra=NULL) x
    arpack(f, options=list(n=10, nev=2, ncv=4), sym=TRUE)

    # Graph laplacian of a star graph (undirected), n>=2
    # Note that this is a linear operation
    f <- function(x, extra=NULL) {
      y <- x
      y[1] <- (length(x)-1)*x[1] - sum(x[-1])
      for (i in 2:length(x)) {
        y[i] <- x[i] - x[1]
      }
      y
    }

    arpack(f, options=list(n=10, nev=1, ncv=3), sym=TRUE)

    # double check
    eigen(graph.laplacian(graph.star(10, mode="undirected")))

[Package igraph version 0.5.2 Index]