|
|
|
Professor:
Prof. Martin H. Gutknecht
Date: 20.10.2007
Project Title:
Block Krylov Space Methods for Indefinite Hermitian Linear Systems
Summary:
Two of the standard sparse linear solvers for indefinite Hermitian
linear systems are the two closely related algorithms MINRES and
SYMMLQ introduced by Paige and Saunders (1975).
A formal generalization of these to block methods for systems with
multiple right-hand sides is quite straightforward.
However, the possibility of intersecting Krylov subspaces (that is,
linear dependence of basis vectors for Krylov subspaces with different
starting vectors, but the same matrix) can cause also for these
Krylov space methods serious difficulties. In the diploma thesis (at ETH)
of Thomas Schmelzer a breakthrough in the understanding of the
effects of deflation in the symmetric block Lanczos process was
achieved: the devastating effect of ignoring deflation is not the
(very unlikely) breakdown of the QR decomposition of the generated
block tridiagonal (or banded) matrix needed in MINRES and SYMMLQ,
but the complete loss of orthogonality of the basis created.
This loss has then a strong effect on the convergence of block
MINRES and SYMMLQ.
The situation is different for block GMRES and ``ordinary'' GMRES
and MINRES.
Another aspect of the problem is the updating of the QR decomposition
of the block Hessenberg matrices that are generated by the block Arnoldi
process. Replacing the normally used Givens rotations by Householder
reflections can speed up this task dramatically.