Project page: http://www.cs.wm.edu/~andreas/CSUMS/eigvals.html
Topic description: The eigenvalue problem is central in many scientific and engineering applications. Whether we study the stability of bridges, the resonant frequencies of electromagnetic waves, data mine the web for the most suitable answer, or simply understanding matter itself through the Schrondinger equation, we have to solve eigenvalue problems. For most of these problems the sizes of the matrices involved are humongous; billion by billion is not unheard of nowadays.
For these sizes we cannot hope to find but only a few eigenvalues and
eigenvectors. This is performed by iterative methods. The most basic is the
power method.
Given a matrix A, start with a vector v and produce the vector sequences:
x, Ax, A(Ax), A( A( Ax)), ...
in other words just powers of A multiplied with x. The sequence converges to
the eigenvector direction with largest modulus eigenvalue. The problem is that
it is slow.
For Hermitian or real symmetric eigenvalue problems the Lanczos method is the
method that considers the best approximation to eigenvectors from the space of
all power iterates:
{x, Ax, A(Ax), A( A( Ax)), ... }
This simple idea can be performed with a three term recurrence, yet it is
still optimal!
The problem with Lanczos is that it must store the above vectors (memory) and it becomes numerical unstable as it iterates. This is the reason why most methods today restart Lanczos after certain number of steps, thus losing convergence speed.
Research opportunity: Recently we have devised a technique that seems to avoid all the bad problems of Lanczos, that uses constant memory, yet still converges optimally.
Holy grail? Are the claims true? Perhaps. This can be verified by simple matlab programs. If they are, can we prove optimality? Near optimality? Anything?
Prerequisities: Math 211 Linear Algebra, Matlab or C/C++ programming skills.
Suggested prerequisities: Math 413/414 or some numerical analysis background
Contact: Andreas Stathopoulos
Last updated at Wednesday, 09-Apr-2008 15:57:04 EDT.