eigs

Largest eigenvalues and eigenvectors of matrix

Syntax

d = eigs(A)
[V,D] = eigs(A)
[V,D,flag] = eigs(A)
eigs(A,B)
eigs(A,k)
eigs(A,B,k)
eigs(A,k,sigma)
eigs(A,B,k,sigma)
eigs(A,K,sigma,opts)
eigs(A,B,k,sigma,opts)
eigs(Afun,n,...)

Description

d = eigs(A) returns a vector of A's six largest magnitude eigenvalues. A must be a square matrix. A should be large and sparse, though eigs will work on full matrices as well. See Tips below.

[V,D] = eigs(A) returns a diagonal matrix D of A's six largest magnitude eigenvalues and a matrix V whose columns are the corresponding eigenvectors.

[V,D,flag] = eigs(A) also returns a convergence flag. If flag is 0 then all the eigenvalues converged; otherwise not all converged.

eigs(A,B) solves the generalized eigenvalue problem A*V == B*V*D. B must be the same size as A. eigs(A,[],...) indicates the standard eigenvalue problem A*V == V*D.

eigs(A,k) and eigs(A,B,k) return the k largest magnitude eigenvalues.

eigs(A,k,sigma) and eigs(A,B,k,sigma) return k eigenvalues based on sigma, which can take any of the following values:

scalar (real or complex, including 0)

The eigenvalues closest to sigma. If A is a function, Afun must return Y = (A-sigma*B)\x (i.e., Y = A\x when sigma = 0).

'lm'

Largest magnitude (default).

'sm'

Smallest magnitude. Same as sigma = 0. If A is a function, Afun must return Y = A\x.

For real symmetric A and symmetric positive-definite B, the following are also options:

'la'

Largest algebraic

'sa'

Smallest algebraic

'be'

Both ends (one more from high end if k is odd)

For nonsymmetric and complex problems, the following are also options:

'lr'

Largest real part

'sr'

Smallest real part

'li'

Largest imaginary part

'si'

Smallest imaginary part

    Note   The syntax eigs(A,k,...) is not valid when A is scalar. To pass a value for k, you must specify B as the second argument and k as the third (eigs(A,B,k,...)). If necessary, you can set B equal to [], the default.

eigs(A,K,sigma,opts) and eigs(A,B,k,sigma,opts) specify an options structure. Default values are shown in brackets ({}).

Parameter

Description

Values

opts.issym

1 if A or A-sigma*B represented by Afun is symmetric, 0 otherwise.

[{0} | 1]

opts.isreal

1 if A or A-sigma*B represented by Afun is real, 0 otherwise.

[0 | {1}]

opts.tol

Convergence: Ritz estimate residual <= tol*norm(A).

[scalar | {eps}]

opts.maxit

Maximum number of iterations.

[integer | {300}]

opts.p

Number of Lanczos basis vectors.
p >= 2k (p >= 2k+1 real nonsymmetric) advised. p must satisfy k < p <= n for real symmetric, k+1 < p <= n otherwise.
Note: If you do not specify a p value, the default algorithm uses at least 20 Lanczos vectors.

[integer | {2*k}]

opts.v0

Starting vector.

[n-by-1 vector | {randomly generated by rand}]

opts.disp

Diagnostic information display level.

[{0} | 1 | 2]

opts.cholB

1 if B is really its Cholesky factor chol(B), 0 otherwise.

[{0} | 1]

opts.permB

Permutation vector permB if sparse B is really chol(B(permB,permB)).

[permB | {1:n}]

eigs(Afun,n,...) accepts a function handle, Afun, instead of the matrix A.

y = Afun(x) should return:

A*x

if sigma is not specified, or is a string other than 'sm'

A\x

if sigma is 0 or 'sm'

(A-sigma*I)\x

if sigma is a nonzero scalar (standard eigenvalue problem). I is an identity matrix of the same size as A.

(A-sigma*B)\x

if sigma is a nonzero scalar (generalized eigenvalue problem)

Parameterizing Functions explains how to provide additional parameters to the function Afun, if necessary.

The matrix A, A-sigma*I or A-sigma*B represented by Afun is assumed to be real and nonsymmetric unless specified otherwise by opts.isreal and opts.issym. In all the eigs syntaxes, eigs(A,...) can be replaced by eigs(Afun,n,...).

Examples

Smallest Eigenvalues of Sparse Matrix

A = delsq(numgrid('C',15));  
d1 = eigs(A,5,'sm')

returns

d1 =
    0.5520
    0.4787
    0.3469
    0.2676
    0.1334

Smallest Eigenvalues of Function-Generated Sparse Matrix

This example replaces the matrix A in example 1 with a handle to a function dnRk. The example is contained in file run_eigs that

  • Calls eigs with the function handle @dnRk as its first argument.

  • Contains dnRk as a nested function, so that all variables in run_eigs are available to dnRk.

The following shows the code for run_eigs:

function d2 = run_eigs
n = 139;  
opts.issym = 1;
R = 'C';
k = 15;
d2 = eigs(@dnRk,n,5,'sm',opts);
 
    function y = dnRk(x)
        y = (delsq(numgrid(R,k))) \ x;
    end
end

Largest Eigenvalue Pairs of Sparse Matrix

west0479 is a real-valued 479-by-479 sparse matrix with both real and complex pairs of conjugate eigenvalues. eig computes all 479 eigenvalues. eigs easily picks out the largest magnitude eigenvalues.

This plot shows the 8 largest magnitude eigenvalues of west0479 as computed by eig and eigs.

load west0479
d = eig(full(west0479));
dlm = eigs(west0479,8);
[dum,ind] = sort(abs(d));
plot(dlm,'k+')
hold on
plot(d(ind(end-7:end)),'ks')
hold off
legend('eigs(west0479,8)','eig(full(west0479))')

Repeated Eigenvalues of Symmetric Positive Definite Sparse Matrix

A = delsq(numgrid('C',30)) is a symmetric positive definite matrix of size 632 with eigenvalues reasonably well-distributed in the interval (0 8), but with 18 eigenvalues repeated at 4.

Use the eig function to compute all 632 eigenvalues, and the eigs function to compute the six largest and smallest magnitude eigenvalues.

A = delsq(numgrid('C',30));
d = sort(eig(full(A)));
dlm = eigs(A);
dsm = eigs(A,6,'sa');

Plot the results from eig and eigs for the six largest and smallest magnitude eigenvalues.

subplot(2,1,1)
plot(dlm,'k+')
hold on
plot(d(end:-1:end-5),'ks')
hold off
legend('eigs(A)','eig(full(A))',3)
xlim([0.5 6.5])

subplot(2,1,2)
plot(dsm,'k+')
hold on
plot(d(1:6),'ks')
hold off
legend('eigs(A,6,''sa'')','eig(full(A))',2)
xlim([0.5 6.5])

The repeated eigenvalue at 4 must be handled more carefully. The call eigs(A,20,4.0) to compute 20 eigenvalues near 4.0 tries to find eigenvalues of A - 4.0*I. This involves divisions of the form 1/(lambda - 4.0), where lambda is an estimate of an eigenvalue of A. As lambda gets closer to 4.0, eigs fails. We must use sigma near but not equal to 4 to find those eigenvalues.

sigma = 4 - 1e-6;
D = sort(eigs(A,20,sigma));

The plot below shows the 20 eigenvalues closest to 4 that were computed by eig, along with the 20 eigenvalues closest to 4 - 1e-6 that were computed by eigs.

figure(2)
plot(d(307:326),'ks')
hold on
plot(D,'k+')
hold off
legend('eig(A)','eigs(A,20,sigma)')
title('18 Repeated Eigenvalues of A')

More About

expand all

Tips

d = eigs(A,k) is not a substitute for

d = eig(full(A))
d = sort(d)
d = d(end-k+1:end)

but is most appropriate for large sparse matrices. If the problem fits into memory, it may be quicker to use eig(full(A)).

Unless you provide a start vector with opts.v0, the default start vector is generated by rand, possibly leading to different iterations each run, and perhaps even different convergence behavior. In order to control this, specify your start vector via opts.v0.

References

[1] Lehoucq, R.B. and D.C. Sorensen, "Deflation Techniques for an Implicitly Re-Started Arnoldi Iteration," SIAM J. Matrix Analysis and Applications, Vol. 17, 1996, pp. 789–821.

[2] Sorensen, D.C., "Implicit Application of Polynomial Filters in a k-Step Arnoldi Method," SIAM J. Matrix Analysis and Applications, Vol. 13, 1992, pp. 357–385.

See Also

| |

Was this topic helpful?