next up previous contents index
Next: Algorithm. Up: Generalized Hermitian Eigenvalue Problems Previous: Rayleigh Quotient Iteration.   Contents   Index


Lanczos Methods
  A. Ruhe

There are several variants of the Lanczos algorithm for the GHEP (5.1). Theoretically they correspond to a reformulation of (5.1) as a standard problem $Cy=\theta y$, with a matrix $C$ chosen as either $C=B^{-1}A$, which corresponds to a direct iteration, or $C=BA^{-1}$, which corresponds to inverse iteration. We will actually study the slightly more general formulation $C=B(A-\sigma B)^{-1}$, shift-and-invert iteration. This is the variant that is preferred in most practical cases because it gives fast convergence to eigenvalues close to the target value $\sigma$, provided that we can solve linear systems with the shifted matrix.

The cause for using shift-and-invert iterations is stronger in this generalized case (5.1) than in the standard (4.1), since also a direct iteration needs solution of linear systems in each step, now with $B$ as a matrix. Even if $B$ most often is better conditioned than $A$, e.g., when $B$ stands for a mass matrix in a vibration problem, it is only when $B$ has a much simpler structure, like being diagonal, that direct iterations need substantially less work in each step than shift-and-invert iterations.

In all the variants, a basis of the Krylov subspace,

\begin{displaymath}
{\cal K}^j(C,x)=\mbox{span}\{x,Cx,C^2x,\dots,C^{j-1}x\}\;,
\end{displaymath}

is built up one column at a time, alternately solving systems and doing matrix-vector multiplications.



Subsections
next up previous contents index
Next: Algorithm. Up: Generalized Hermitian Eigenvalue Problems Previous: Rayleigh Quotient Iteration.   Contents   Index
Susan Blackford 2000-11-20