From: "N. Shamsundar" <shamsundar@uh.edu>
Subject: Re: Lowest few eigenvalues (and eigenvectors) of large hermitian/Symmetric Martix
Date: Sun, 24 Oct 1999 13:51:33 -0500
Newsgroups: sci.math.num-analysis
Keywords: deflating a matrix after some eigenvalues are found

Regardless of which algorithm you use to compute the smallest
eigenvalue, there is a simple technique to "deflate" the matrix
after the smallest eigenvalue has been found.

The deflation is performed as follows.  Let x1 be an eigenvector
corresponding to the eigenvalue.  Do a Householder reflection of
your nXn matrix A with regard to this vector, i.e., find U=I - 2
x1 x1^T/x1^T x1, form A1=UAU^T, and drop the first row and first
column in A1.  The remaining (n-1)X(n-1) matrix has as its
smallest eigenvalue the second smallest eigenvalue of A.  The
procedure can be applied recursively to find the next smaller
eigenvalue, and so on.

Note that since U is rank-1, the matrix multiplications in UAU^T
can be reduced to matrix-vector multiplications and rank-one or
rank-two updates.

--
N. Shamsundar
University of Houston
shamsundar@uh.edu

Ender Aysal wrote in message
<381287B1.9C023A1C@wupper-magic.de>...
>Hi
>
>I wanted to add that i am programming in C.
>The problem is also, that the matrix is too big to be stored in memory. But
>I have a procedure which acts on a Vector like this matrix.
>So lanczos was very good, because i just needet to store two vectors in
>memory.
>So, is there perhaps anyone who knows how to make lanczos calculate a few
>eigenvectors more?
>Or is there any other algorithm i could programm?
>
>Thanks
>
>Ender Aysal
==============================================================================

From: Steffen Boerm <sbo@numerik.uni-kiel.de>
Subject: Re: Lowest few eigenvalues (and eigenvectors) of large hermitian/Symmetric Martix
Date: 25 Oct 1999 09:40:37 +0200
Newsgroups: sci.math.num-analysis

"N. Shamsundar" <shamsundar@uh.edu> writes:

> Regardless of which algorithm you use to compute the smallest
> eigenvalue, there is a simple technique to "deflate" the matrix
> after the smallest eigenvalue has been found.

Since the matrix apparently isn't stored in memory, an explicit
deflations seems not to be applicable.

But it is possible to remove a certain eigenvector from the space
that the Lanczos methods considers by simply making sure that the
start vector doesn't contain a component of this eigenvector.

If v_0,...,v_{q-1} are q pairwise orthogonal, normalized eigenvectors
computed in preceeding Lanzcos procedures, we can use

  create_start_vector(x);
  for(i=0; i<q; i++) {
    s = scalar_product(x, v[i]);
    linear_combination(x, -s, v[i]);
  }
  lanczos(x);

to find the smallest eigenvectors of the remaining space.

This kind of "deflation" works (at least in theory) for all methods
based on Krylov spaces as long as the matrix is symmetric.

If the matrix is the result of a finite-element- or finite-
differences-discretization that is elliptic, I would suggest to use
the eigenvalue multigrid from Hackbusch, "Multigrid Methods and
Applications". It's of optimal complexity for low-frequency eigenvectors
and only needs the evaluation of matrix-vector-products.

Best regards,
cu, Steffen 8-)

-- 
Steffen Boerm
EMail: sbo@numerik.uni-kiel.de
  WWW: http://www.numerik.uni-kiel.de/~sbo/