arpack {igraph} | R Documentation |
Interface to the ARPACK library for calculating eigenvectors of sparse matrices
arpack(func, extra = NULL, sym = FALSE, options = igraph.arpack.default, env = parent.frame(), complex=!sym) arpack.unpack.complex(vectors, values, nev)
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 argument to supply to |
sym |
Logical scalar, whether the input matrix is
symmetric. Always supply |
options |
Options to ARPACK, a named list to overwrite some of the default option values. See details below. |
env |
The environment in which |
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 |
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. |
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:
bmatCharacter 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.
nNumeric 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.)
whichSpecify 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
’.
nevNumeric scalar. The number of eigenvalues to be computed.
tolNumeric 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.
ncvNumber of Lanczos vectors to be generated.
ldvNumberic scalar. It should be set to zero in the current implementation.
ishiftEither 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.
maxiterMaximum number of Arnoldi update iterations allowed.
nbBlocksize to be used in the recurrence. Please always leave this on the default value, one.
modeThe type of the eigenproblem to be solved. Possible values if the input matrix is symmetric:
1A*x=lambda*x, A is symmetric.
2A*x=lambda*M*x, A is symmetric, M is symmetric positive definite.
3K*x=lambda*M*x, K is symmetric, M is symmetric positive semi-definite.
4K*x=lambda*KG*x, K is symmetric positive semi-definite, KG is symmetric indefinite.
5A*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:
1A*x=lambda*x.
2A*x=lambda*M*x, M is symmetric positive definite.
3A*x=lambda*M*x, M is symmetric semi-definite.
4A*x=lambda*M*x, M is symmetric semi-definite.
Please note that only mode==1
was tested and other values
might not work properly.
startNot used currently. Later it be used to set a starting vector.
sigmaNot used currently.
sigmaiNot use currently.
On output the following additional fields are added:
infoError flag of ARPACK. Possible values:
0Normal exit.
1Maximum number of iterations taken.
3No 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.
iterNumber of Arnoldi iterations taken.
nconvNumber of “converged” Ritz values. This represents the number of Ritz values that satisfy the convergence critetion.
numopTotal number of matrix-vector multiplications.
numopbNot used currently.
numreoTotal 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
.
A named list with the following members:
values |
Numeric vector, the desired eigenvalues. |
vectors |
Numeric matrix, the desired eigenvectors as
columns. If |
options |
A named list with the supplied |
Rich Lehoucq, Kristi Maschhoff, Danny Sorensen, Chao Yang for ARPACK, Gabor Csardi csardi@rmki.kfki.hu for the R interface.
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).
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/.
# 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")))