From: "Chip Eastham" <eastham@bellsouth.net>
Subject: Re: Sparce matrix and eigenvalues
Date: Tue, 23 Jan 2001 12:47:41 -0500
Newsgroups: sci.math
Summary: Eigenvalue computations for sparse matrices (Lanczos, Arnoldi)

"Apostolos" <apostolos-no-@programmer.net> wrote in message
news:Xns90318B513programmernet@194.177.210.211...
> Hi,
>
> i wonder if anybody could give a hint about any techniques used to
> determine the eigenvalues of a sparce matrix. What i am actually looking
> for is techniques that take advantage of the fact that the matrix is sparce
> in order to compute faster the eigenvalues.
>

Consider the most basic approach, the power method:

x_{n+1} = (1/||Ax_n||) Ax_n

Then {x_n} should converge under mild conditions to an eigenvector
for the dominant eigenvalue of A.  The sparsenesss of A can easily
be exploited in forming the matrix-vector products.

Similarly the inverse power method, i.e. solving:

Ax_{n+1} = x_n

with appropriate renormalization, can find the "smallest" eigenvalue.

As with root isolation for polynomials, other eigenvector/eigenvalue
pairs can be located by combining the inverse power method with
shifts.  The Lanczos method can be understood as a kind of block
version of this.  Golub and Van Loan give an introduction to the
extension of Lanczos methods to unsymmetric matrices in Sec. 9.4
of Matrix Computations.  Whether this is attractive depends on
how much of the spectrum of the matrix you need to find.

Where symmetric Lanczos centers on an orthogonal similarity
transformation to make an initial reduction to tridiagonal form,
the "Arnoldi process" settles for upper Hessenberg reduction
(by orthogonal similarity).  Another tack, which goes back at
least to Wilkinson, is to use more general similarity matrices
to reduce an unsymmetric matrix to tridiagonal form.

How does this relate to sparsity?  Of course once a matrix has
been reduced to tridiagonal form, all sparsity of the original
matrix is subsumed.  If I remember correctly, at least for the
symmetric case it's possible to take advantage of sparsity in
the reduction to tridiagonal form using Givens rather than
Householder matrices.  In the unsymmetric case it seems more
difficult to exploit sparsity.

Regards,
Chip