Solving the Reduced Eigenvalue Problems

Recall that Algorithm 7.17 produces a complex symmetric tridiagonal matrix $T_j$ and that, in order to obtain approximate eigenvalues of $A$, at least some of the eigenvalues of $T_j$ need to be computed. Using the QR algorithm for the task of computing all eigenvalues of $T_j$ does not exploit the tridiagonal structure of $T_j$. Indeed, after one step of the QR algorithm, in general, the tridiagonal structure of $T_j$ 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 $Q$ and a lower triangular matrix $L$. However, since $Q$ is not unitary in general, carefully chosen heuristics are needed in order to monitor and maintain numerical stability; we refer the reader to [94] 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 $T_j$ will be destroyed as soon as a look-ahead step occurs. The matrix $V_j$ of Lanczos vectors is then no longer complex orthogonal, but instead $D_j = V_j^T V_j$ 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 $1 \times 1$ ``block'' occurs whenever a regular Lanczos step (without look-ahead) is possible, and each ``true'' block of size bigger than $1$ corresponds to a look-ahead step. Furthermore, instead of (7.101), one now has the relation

$$D_j T_j = V_j^T A V_j,$$

which shows that $D_j T_j$ is complex symmetric. In addition, the matrix $D_j T_j$ is block tridiagonal with diagonal blocks of the same size as $D_j$. Therefore, in the look-ahead case, instead of the standard eigenvalue problem (7.100), one could solve the equivalent complex symmetric generalized eigenvalue problem

$$D_j T_j z_i^{(j)} = \theta_i^{(j)} D_j z_i^{(j)},\quad i=1,2,\ldots,j.$$ (208)

Here, both matrices $D_j T_j$ and $D_j$ are complex symmetric, $D_j T_j$ is block tridiagonal, and $D_j$ is block diagonal. However, it is not clear how to exploit this special structure when solving (7.102).