igraph (version 0.7.0)

arpack: 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

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

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.

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.

concept

• Eigenvalues
• Eigenvectors
• ARPACK

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: [object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],On output the following additional fields are added: [object Object],[object Object],[object Object],[object Object],[object Object],[object Object] 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.

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")))

## First three eigenvalues of the adjacency matrix of a graph
## We need the 'Matrix' package for this
if (require(Matrix)) {
  g <- erdos.renyi.game(1000, 5/1000)
  M <- get.adjacency(g, sparse=TRUE)
  f2 <- function(x, extra=NULL) { cat("."); as.vector(M %*% x) }
  baev <- arpack(f2, sym=TRUE, options=list(n=vcount(g), nev=3, ncv=8,
                                  which="LM", maxiter=200))
}