eigs: Find a Specified Number of Eigenvalues/vectors of a Square Matrix

Description

Given an $n$ by $n$ matrix $A$, function eigs() can calculate a specified number of eigenvalues and eigenvectors of $A$. Users can specify the selection criterion by argument which, e.g., choosing the $k$ largest or smallest eigenvalues and the corresponding eigenvectors.

Currently eigs() supports matrices of the following classes:

`matrix`	The most commonly used matrix type, defined in the base package.
`dgeMatrix`	General matrix, equivalent to `matrix`, defined in the Matrix package.
`dgCMatrix`	Column oriented sparse matrix, defined in the Matrix package.
`dgRMatrix`	Row oriented sparse matrix, defined in the Matrix package.
`dsyMatrix`	Symmetric matrix, defined in the Matrix package.
`dsCMatrix`	Symmetric column oriented sparse matrix, defined in the Matrix package.
`dsRMatrix`	Symmetric row oriented sparse matrix, defined in the Matrix package.
`function`	Implicitly specify the matrix through a function that has the effect of calculating $f(x)=Ax$. See section Function Interface for details.

eigs_sym() assumes the matrix is symmetric, and only the lower triangle (or upper triangle, which is controlled by the argument lower) is used for computation, which guarantees that the eigenvalues and eigenvectors are real, and in general results in faster and more stable computation. One exception is when A is a function, in which case the user is responsible for the symmetry of the operator.

eigs_sym() supports "matrix", "dgeMatrix", "dgCMatrix", "dgRMatrix" and "function" typed matrices.

Usage

eigs(A, k, which = "LM", sigma = NULL, opts = list(), ...)
# S3 method for matrix
eigs(A, k, which = "LM", sigma = NULL, opts = list(), ...)
# S3 method for dgeMatrix
eigs(A, k, which = "LM", sigma = NULL, opts = list(), ...)
# S3 method for dsyMatrix
eigs(A, k, which = "LM", sigma = NULL, opts = list(), ...)
# S3 method for dgCMatrix
eigs(A, k, which = "LM", sigma = NULL, opts = list(), ...)
# S3 method for dsCMatrix
eigs(A, k, which = "LM", sigma = NULL, opts = list(), ...)
# S3 method for dgRMatrix
eigs(A, k, which = "LM", sigma = NULL, opts = list(), ...)
# S3 method for dsRMatrix
eigs(A, k, which = "LM", sigma = NULL, opts = list(), ...)
# S3 method for `function`
eigs(
  A,
  k,
  which = "LM",
  sigma = NULL,
  opts = list(),
  ...,
  n = NULL,
  args = NULL
)
eigs_sym(A, k, which = "LM", sigma = NULL, opts = list(),
   lower = TRUE, ...)
# S3 method for `function`
eigs_sym(
  A,
  k,
  which = "LM",
  sigma = NULL,
  opts = list(),
  lower = TRUE,
  ...,
  n = NULL,
  args = NULL
)

Value

A list of converged eigenvalues and eigenvectors.

values: Computed eigenvalues.
vectors: Computed eigenvectors. vectors[, j] corresponds to values[j].
nconv: Number of converged eigenvalues.
niter: Number of iterations used in the computation.
nops: Number of matrix operations used in the computation.

Arguments

A: The matrix whose eigenvalues/vectors are to be computed. It can also be a function which receives a vector $x$ and calculates $Ax$. See section Function Interface for details.
k: Number of eigenvalues requested.
which: Selection criterion. See Details below.
sigma: Shift parameter. See section Shift-And-Invert Mode.
opts: Control parameters related to the computing algorithm. See Details below.
...: Arguments for specialized S3 function calls, for example lower, n and args.
n: Only used when A is a function, to specify the dimension of the implicit matrix. See section Function Interface for details.
args: Only used when A is a function. This argument will be passed to the A function when it is called. See section Function Interface for details.
lower: For symmetric matrices, should the lower triangle or upper triangle be used.

Shift-And-Invert Mode

The sigma argument is used in the shift-and-invert mode.

When sigma is not NULL, the selection criteria specified by argument which will apply to

$$\frac{1}{\lambda-\sigma}$$

where $\lambda$'s are the eigenvalues of $A$. This mode is useful when user wants to find eigenvalues closest to a given number. For example, if $\sigma=0$, then which = "LM" will select the largest values of $1/|\lambda|$, which turns out to select eigenvalues of $A$ that have the smallest magnitude. The result of using which = "LM", sigma = 0 will be the same as which = "SM", but the former one is preferable in that eigs() is good at finding large eigenvalues rather than small ones. More explanation of the shift-and-invert mode can be found in the SciPy document, https://docs.scipy.org/doc/scipy/tutorial/arpack.html.

Function Interface

The matrix $A$ can be specified through a function with the definition

function(x, args)
{
    ## should return A %*% x
}

which receives a vector x as an argument and returns a vector of the same length. The function should have the effect of calculating $Ax$, and extra arguments can be passed in through the args parameter. In eigs(), user should also provide the dimension of the implicit matrix through the argument n.

Author

Yixuan Qiu https://statr.me

Jiali Mei vermouthmjl@gmail.com

Details

The which argument is a character string that specifies the type of eigenvalues to be computed. Possible values are:

"LM"	The $k$ eigenvalues with largest magnitude. Here the magnitude means the Euclidean norm of complex numbers.
"SM"	The $k$ eigenvalues with smallest magnitude.
"LR"	The $k$ eigenvalues with largest real part.
"SR"	The $k$ eigenvalues with smallest real part.
"LI"	The $k$ eigenvalues with largest imaginary part.
"SI"	The $k$ eigenvalues with smallest imaginary part.
"LA"	The $k$ largest (algebraic) eigenvalues, considering any negative sign.
"SA"	The $k$ smallest (algebraic) eigenvalues, considering any negative sign.
"BE"	Compute $k$ eigenvalues, half from each end of the spectrum. When $k$ is odd, compute more from the high and then from the low end.

eigs() with matrix types "matrix", "dgeMatrix", "dgCMatrix" and "dgRMatrix" can use "LM", "SM", "LR", "SR", "LI" and "SI".

eigs_sym() with all supported matrix types, and eigs() with symmetric matrix types ("dsyMatrix", "dsCMatrix", and "dsRMatrix") can use "LM", "SM", "LA", "SA" and "BE".

The opts argument is a list that can supply any of the following parameters:

ncv: Number of Lanzcos basis vectors to use. More vectors will result in faster convergence, but with greater memory use. For general matrix, ncv must satisfy $k+2\le ncv \le n$, and for symmetric matrix, the constraint is $k < ncv \le n$. Default is min(n, max(2*k+1, 20)).
tol: Precision parameter. Default is 1e-10.
maxitr: Maximum number of iterations. Default is 1000.
retvec: Whether to compute eigenvectors. If FALSE, only calculate and return eigenvalues.
initvec: Initial vector of length $n$ supplied to the Arnoldi/Lanczos iteration. It may speed up the convergence if initvec is close to an eigenvector of $A$.

Examples

Run this code

library(Matrix)
n = 20
k = 5

## general matrices have complex eigenvalues
set.seed(111)
A1 = matrix(rnorm(n^2), n)  ## class "matrix"
A2 = Matrix(A1)             ## class "dgeMatrix"

eigs(A1, k)
eigs(A2, k, opts = list(retvec = FALSE))  ## eigenvalues only

## Sparse matrices
A1[sample(n^2, n^2 / 2)] = 0
A3 = as(A1, "dgCMatrix")
A4 = as(A1, "dgRMatrix")

eigs(A3, k)
eigs(A4, k)

## Function interface
f = function(x, args)
{
    as.numeric(args %*% x)
}
eigs(f, k, n = n, args = A3)

## Symmetric matrices have real eigenvalues
A5 = crossprod(A1)
eigs_sym(A5, k)

## Find the smallest (in absolute value) k eigenvalues of A5
eigs_sym(A5, k, which = "SM")

## Another way to do this: use the sigma argument
eigs_sym(A5, k, sigma = 0)

## The results should be the same,
## but the latter method is far more stable on large matrices

Run the code above in your browser using DataLab

"LM"	The \(k\) eigenvalues with largest magnitude. Here the magnitude means the Euclidean norm of complex numbers.
"SM"	The \(k\) eigenvalues with smallest magnitude.
"LR"	The \(k\) eigenvalues with largest real part.
"SR"	The \(k\) eigenvalues with smallest real part.
"LI"	The \(k\) eigenvalues with largest imaginary part.
"SI"	The \(k\) eigenvalues with smallest imaginary part.
"LA"	The \(k\) largest (algebraic) eigenvalues, considering any negative sign.
"SA"	The \(k\) smallest (algebraic) eigenvalues, considering any negative sign.
"BE"	Compute \(k\) eigenvalues, half from each end of the spectrum. When \(k\) is odd, compute more from the high and then from the low end.