     Next: Software Availability Up: Lanczos Method for Complex Previous: Algorithm   Contents   Index

## Solving the Reduced Eigenvalue Problems

Recall that Algorithm 7.17 produces a complex symmetric tridiagonal matrix and that, in order to obtain approximate eigenvalues of , at least some of the eigenvalues of need to be computed. Using the QR algorithm for the task of computing all eigenvalues of does not exploit the tridiagonal structure of . Indeed, after one step of the QR algorithm, in general, the tridiagonal structure of will have been destroyed and one obtains a full upper Hessenberg matrix, just as in the case of QR for general NHEPs. Cullum and Willoughby [91,92,94] developed a QL procedure for complex symmetric tridiagonal matrices that exploits this special structure. The algorithm is based on factorizations of complex symmetric tridiagonal matrices into a complex orthogonal matrix and a lower triangular matrix . However, since is not unitary in general, carefully chosen heuristics are needed in order to monitor and maintain numerical stability; we refer the reader to  for a detailed description of the QL procedure.

If the complex symmetric Lanczos method is run with look-ahead, then the complex symmetric tridiagonal structure of the Lanczos matrix will be destroyed as soon as a look-ahead step occurs. The matrix of Lanczos vectors is then no longer complex orthogonal, but instead is a complex symmetric block-diagonal matrix, where the sizes of the diagonal blocks correspond to the lengths of the look-ahead steps. In particular, a block'' occurs whenever a regular Lanczos step (without look-ahead) is possible, and each true'' block of size bigger than corresponds to a look-ahead step. Furthermore, instead of (7.101), one now has the relation which shows that is complex symmetric. In addition, the matrix is block tridiagonal with diagonal blocks of the same size as . Therefore, in the look-ahead case, instead of the standard eigenvalue problem (7.100), one could solve the equivalent complex symmetric generalized eigenvalue problem (208)

Here, both matrices and are complex symmetric, is block tridiagonal, and is block diagonal. However, it is not clear how to exploit this special structure when solving (7.102).     Next: Software Availability Up: Lanczos Method for Complex Previous: Algorithm   Contents   Index
Susan Blackford 2000-11-20