arpack                package:igraph                R Documentation

_A_R_P_A_C_K _e_i_g_e_n_v_e_c_t_o_r _c_a_l_c_u_l_a_t_i_o_n

_D_e_s_c_r_i_p_t_i_o_n:

     Interface to the ARPACK library for calculating eigenvectors of
     sparse matrices

_U_s_a_g_e:

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

_A_r_g_u_m_e_n_t_s:

    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.

_D_e_t_a_i_l_s:

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

   _b_m_a_t 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.)

   _w_h_i_c_h Specify which eigenvalues/vectors to compute, character
        constant with exactly two characters.

        Possible values for symmetric input matrices:

      ''_L_A'' Compute 'nev' largest (algebraic) eigenvalues.

      ''_S_A'' Compute 'nev' smallest (algebraic) eigenvalues.

      ''_L_M'' Compute 'nev' largest (in magnitude) eigenvalues.

      ''_S_M'' Compute 'nev' smallest (in magnitude) eigenvalues.

      ''_B_E'' 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:

      ''_L_M'' Compute 'nev' eigenvalues of largest magnitude.

      ''_S_M'' Compute 'nev' eigenvalues of smallest magnitude.

      ''_L_R'' Compute 'nev' eigenvalues of largest real part.

      ''_S_R'' Compute 'nev' eigenvalues of smallest real part.

      ''_L_I'' Compute 'nev' eigenvalues of largest imaginary part.

      ''_S_I'' Compute 'nev' eigenvalues of smallest imaginary part.

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

   _n_e_v Numeric scalar. The number of eigenvalues to be computed.

   _t_o_l 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.

   _n_c_v Number of Lanczos vectors to be generated.

   _l_d_v Numberic scalar. It should be set to zero in the current
        implementation.

   _i_s_h_i_f_t 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.

   _m_a_x_i_t_e_r Maximum number of Arnoldi update iterations allowed. 

   _n_b Blocksize to be used in the recurrence. Please always leave this
        on the default value, one.

   _m_o_d_e 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.

   _s_t_a_r_t Not used currently. Later it be used to set a starting vector.

   _s_i_g_m_a Not used currently.

   _s_i_g_m_a_i Not use currently.

        On output the following additional fields are added:

      _i_n_f_o 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.

      _i_t_e_r Number of Arnoldi iterations taken.

      _n_c_o_n_v Number of "converged" Ritz values. This represents the
           number of Ritz values that satisfy the convergence
           critetion. 

      _n_u_m_o_p Total number of matrix-vector multiplications.

      _n_u_m_o_p_b Not used currently.

      _n_u_m_r_e_o 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'.

_V_a_l_u_e:

     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. 

_A_u_t_h_o_r(_s):

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

_R_e_f_e_r_e_n_c_e_s:

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

_S_e_e _A_l_s_o:

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

_E_x_a_m_p_l_e_s:

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

