EVOLUTION-MANAGER

Edit File: arpack.html

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><title>R: ARPACK eigenvector calculation</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<link rel="stylesheet" type="text/css" href="R.css" />
</head><body>

<table width="100%" summary="page for arpack_defaults {igraph}"><tr><td>arpack_defaults {igraph}</td><td style="text-align: right;">R Documentation</td></tr></table>

<h2>ARPACK eigenvector calculation</h2>

<h3>Description</h3>

Interface to the ARPACK library for calculating eigenvectors of sparse
matrices

<h3>Usage</h3>

<pre>
arpack_defaults

arpack(
 func,
 extra = NULL,
 sym = FALSE,
 options = arpack_defaults,
 env = parent.frame(),
 complex = !sym
)
</pre>

<h3>Arguments</h3>

<table summary="R argblock">
<tr valign="top"><td><code>func</code></td>
<td>
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
&ldquo;input matrix&rdquo;. (The input matrix is never given explicitly.) The
second argument is <code>extra</code>.
</td></tr>
<tr valign="top"><td><code>extra</code></td>
<td>
Extra argument to supply to <code>func</code>.
</td></tr>
<tr valign="top"><td><code>sym</code></td>
<td>
Logical scalar, whether the input matrix is symmetric. Always
supply <code>TRUE</code> here if it is, since it can speed up the computation.
</td></tr>
<tr valign="top"><td><code>options</code></td>
<td>
Options to ARPACK, a named list to overwrite some of the
default option values. See details below.
</td></tr>
<tr valign="top"><td><code>env</code></td>
<td>
The environment in which <code>func</code> will be evaluated.
</td></tr>
<tr valign="top"><td><code>complex</code></td>
<td>
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 <code>FALSE</code> here.
</td></tr>
</table>

<h3>Format</h3>

An object of class <code>list</code> of length 14.

<h3>Details</h3>

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 <code>w &lt;- Av</code> requires order n
rather than the usual order n^2 floating point operations.

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 <code>fun</code>
argument is expected to perform this product. If the product can be done
efficiently, e.g. if the matrix is sparse, then <code>arpack</code> is usually
able to calculate the eigenvalues very quickly.

The <code>options</code> 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:

<dl>
<dt>bmat</dt><dd>Character constant, possible values: &lsquo;<code>I</code>&rsquo;, standard
eigenvalue problem, A*x=lambda*x; and &lsquo;<code>G</code>&rsquo;,
generalized eigenvalue problem, A*x=lambda B*x.
Currently only &lsquo;<code>I</code>&rsquo; is supported.
</dd> <dt>n</dt><dd>Numeric scalar. The
dimension of the eigenproblem. You only need to set this if you call
<code><a href="arpack.html">arpack</a></code> directly. (I.e. not needed for
<code><a href="eigen_centrality.html">eigen_centrality</a></code>, <code><a href="page_rank.html">page_rank</a></code>, etc.)
</dd>
<dt>which</dt><dd>Specify which eigenvalues/vectors to compute, character
constant with exactly two characters.

Possible values for symmetric input matrices:

<dl>
<dt>&quot;LA&quot;</dt><dd>Compute <code>nev</code> largest (algebraic) eigenvalues.
</dd>
<dt>&quot;SA&quot;</dt><dd>Compute <code>nev</code> smallest (algebraic)
eigenvalues.
</dd> <dt>&quot;LM&quot;</dt><dd>Compute <code>nev</code> largest (in
magnitude) eigenvalues.
</dd> <dt>&quot;SM&quot;</dt><dd>Compute <code>nev</code> smallest
(in magnitude) eigenvalues.
</dd> <dt>&quot;BE&quot;</dt><dd>Compute <code>nev</code>
eigenvalues, half from each end of the spectrum. When <code>nev</code> is odd,
compute one more from the high end than from the low end.
</dd> </dl>

Possible values for non-symmetric input matrices:

<dl>
<dt>&quot;LM&quot;</dt><dd>Compute <code>nev</code> eigenvalues of largest
magnitude.
</dd> <dt>&quot;SM&quot;</dt><dd>Compute <code>nev</code> eigenvalues of
smallest magnitude.
</dd> <dt>&quot;LR&quot;</dt><dd>Compute <code>nev</code> eigenvalues
of largest real part.
</dd> <dt>&quot;SR&quot;</dt><dd>Compute <code>nev</code>
eigenvalues of smallest real part.
</dd> <dt>&quot;LI&quot;</dt><dd>Compute
<code>nev</code> eigenvalues of largest imaginary part.
</dd>
<dt>&quot;SI&quot;</dt><dd>Compute <code>nev</code> eigenvalues of smallest imaginary
part.
</dd> </dl>

This parameter is sometimes overwritten by the various functions, e.g.
<code><a href="page_rank.html">page_rank</a></code> always sets &lsquo;<code>LM</code>&rsquo;. 
</dd>
<dt>nev</dt><dd>Numeric scalar. The number of eigenvalues to be computed.
</dd>
<dt>tol</dt><dd>Numeric scalar. Stopping criterion: the relative accuracy of the
Ritz value is considered acceptable if its error is less than <code>tol</code>
times its estimated value. If this is set to zero then machine precision is
used.
</dd> <dt>ncv</dt><dd>Number of Lanczos vectors to be generated.
</dd>
<dt>ldv</dt><dd>Numberic scalar. It should be set to zero in the current
implementation.
</dd> <dt>ishift</dt><dd>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.
</dd> <dt>maxiter</dt><dd>Maximum number of Arnoldi update iterations
allowed. 
</dd> <dt>nb</dt><dd>Blocksize to be used in the recurrence. Please always
leave this on the default value, one.
</dd> <dt>mode</dt><dd>The type of the
eigenproblem to be solved. Possible values if the input matrix is
symmetric: 
 <dl>
<dt>1</dt><dd>A*x=lambda*x, A is
symmetric.
</dd> <dt>2</dt><dd>A*x=lambda*M*x, A is
symmetric, M is symmetric positive definite.
</dd> <dt>3</dt><dd>K*x=lambda*M*x, K is symmetric, M is symmetric positive
semi-definite.
</dd> <dt>4</dt><dd>K*x=lambda*KG*x, K is
symmetric positive semi-definite, KG is symmetric indefinite.
</dd>
<dt>5</dt><dd>A*x=lambda*M*x, A is symmetric, M
is symmetric positive semi-definite. (Cayley transformed mode.)
</dd> </dl>
 Please
note that only <code>mode==1</code> was tested and other values might not work
properly.

Possible values if the input matrix is not symmetric:

<dl>
<dt>1</dt><dd>A*x=lambda*x.
</dd> <dt>2</dt><dd>A*x=lambda*M*x, M is symmetric positive definite.
</dd>
<dt>3</dt><dd>A*x=lambda*M*x, M is symmetric
semi-definite.
</dd> <dt>4</dt><dd>A*x=lambda*M*x, M is
symmetric semi-definite.
</dd> </dl>
 Please note that only <code>mode==1</code> was tested
and other values might not work properly. 
</dd> <dt>start</dt><dd>Not used
currently. Later it be used to set a starting vector.
</dd> <dt>sigma</dt><dd>Not used
currently.
</dd> <dt>sigmai</dt><dd>Not use currently.
</dd>
</dl>
On output the following additional fields are added:

<dl>
<dt>info</dt><dd>Error flag of ARPACK. Possible values:

<dl>
<dt>0</dt><dd>Normal exit.
</dd> <dt>1</dt><dd>Maximum number of iterations taken.
</dd>
<dt>3</dt><dd>No shifts could be applied during a cycle of the Implicitly
restarted Arnoldi iteration. One possibility is to increase the size of
<code>ncv</code> relative to <code>nev</code>.
</dd> </dl>

ARPACK can return more error conditions than these, but they are converted
to regular igraph errors. 
</dd> <dt>iter</dt><dd>Number of Arnoldi iterations
taken.
</dd> <dt>nconv</dt><dd>Number of &ldquo;converged&rdquo; Ritz values. This
represents the number of Ritz values that satisfy the convergence critetion.

</dd> <dt>numop</dt><dd>Total number of matrix-vector multiplications.
</dd>
<dt>numopb</dt><dd>Not used currently.
</dd> <dt>numreo</dt><dd>Total number of steps of
re-orthogonalization.
</dd> </dl>
 Please see the ARPACK documentation for
additional details.

<h3>Value</h3>

A named list with the following members: 
<table summary="R valueblock">
<tr valign="top"><td><code>values</code></td>
<td>
Numeric
vector, the desired eigenvalues.
</td></tr> <tr valign="top"><td><code>vectors</code></td>
<td>
Numeric matrix, the desired
eigenvectors as columns. If <code>complex=TRUE</code> (the default for
non-symmetric problems), then the matrix is complex.
</td></tr> <tr valign="top"><td><code>options</code></td>
<td>
A named
list with the supplied <code>options</code> and some information about the
performed calculation, including an ARPACK exit code. See the details above.

</td></tr>
</table>

<h3>Author(s)</h3>

Rich Lehoucq, Kristi Maschhoff, Danny Sorensen, Chao Yang for
ARPACK, Gabor Csardi <a href="mailto:csardi.gabor@gmail.com">csardi.gabor@gmail.com</a> for the R interface.

<h3>References</h3>

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 &amp; Y. Saad, Complex Shift and Invert Strategies for Real
Matrices. Linear Algebra and its Applications, vol 88/89, pp 575-595,
(1987).

<code><a href="eigen_centrality.html">eigen_centrality</a></code>, <code><a href="page_rank.html">page_rank</a></code>,
<code><a href="hub_score.html">hub_score</a></code>, <code><a href="cluster_leading_eigen.html">cluster_leading_eigen</a></code> are some of the
functions in igraph that use ARPACK.

<h3>Examples</h3>

<pre>

# Identity matrix
f &lt;- 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&gt;=2
# Note that this is a linear operation
f &lt;- function(x, extra=NULL) {
  y &lt;- x
  y[1] &lt;- (length(x)-1)*x[1] - sum(x[-1])
  for (i in 2:length(x)) {
    y[i] &lt;- x[i] - x[1]
  }
  y
}

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

# double check
eigen(laplacian_matrix(make_star(10, mode="undirected")))

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

<hr /><div style="text-align: center;">[Package igraph version 1.3.5 <a href="00Index.html">Index</a>]</div>
</body></html>