Singular $B$

Special care must be taken when the symmetric indefinite Lanczos procedure is implemented with a singular $B$ matrix. Here we limit our discussion to the case where $H^{-1} B$ is diagonalizable. If $H^{-1} B$ is defective the problem is more complicated and the reader is referred to [161] for details.

When $B$ is singular, $\{A,B\}$ has infinite eigenvalues; the eigenvectors corresponding to the infinite eigenvalues lie in the null space of $B$, while the eigenvectors corresponding to the eigenvalues of interest (i.e., the finite eigenvalues) belong to the range of $H^{-1} B$. Consider the following example:

$$A=\left[\begin{array}{cc} \alpha & \beta\\ \beta & \gamma \... ...B=\left[\begin{array}{cc} 1 & 0 \\ 0 & 0 \end{array}\right].$$

Then

$$H^{-1} B = (A-\sigma B)^{-1}B=\frac{1}{\delta} \left[\begin{array}{cc} \gamma & 0\\ -\beta & 0 \end{array}\right],$$

where $\delta = (\alpha-\sigma)\gamma-\beta^2$. The eigenvalue of $H^{-1} B$ of interest is $\gamma/\delta$ and the corresponding eigenvector $\onebytwo{\gamma}{-\beta}^T$ (the zero eigenvalue corresponds to an infinite eigenvalue of the original problem).

Note that the eigenvector has a component ($-\beta$ in the example) in the null space of $B$ and that the range space of $H^{-1} B$ is independent of $\sigma$. It is important that the Lanczos starting vector $q$ lies in this range space since components outside the space may grow during the Lanczos iteration and contaminate the Ritz vectors.

It is essential that Algorithm 8.4 produce Ritz vectors which lie entirely in the range of $H^{-1} B$. To this end, we recommend a preprocessing step as well as a postprocessing step for Algorithm 8.4.

The initial vector $q$ in Algorithm 8.4 should lie in the range of $H^{-1} B$. For example, one could use the product of $H^{-1} B$ and a random vector. In exact arithmetic, if the initial vector $q$ lies in the range of $H^{-1} B$, then all of the Lanczos vectors $\{q_j\}$ will belong to the range of $H^{-1} B$ [340].

However, in finite precision arithmetic, preprocessing the initial vector $q$ may not be enough to ensure that the Ritz vectors lie in the range of $H^{-1} B$. As the Lanczos iteration progresses, roundoff errors cause the Lanczos vectors to acquire unwanted components in the null space of $B$. There is no cheap way to eliminate these components from the Lanczos vectors, even though the size of the components may be monitored via an inexpensive recurrence derived in [340]. Fortunately, there is a simple postprocessing scheme for purging the undesired components of Ritz vectors which lie in the null space of $B$. The idea is to replace the Ritz vector ${x}_i^{(j)}$ with a multiple of $H^{-1}Bx_i^{(j)}$, which clearly belongs to the range of $H^{-1} B$. In practice, there is no need to explicitly compute the vector $H^{-1}Bx_i^{(j)}$; we may take advantage of quantities which are readily available in the Lanczos procedure to compute a vector parallel to $H^{-1}B {x}_i^{(j)}$. From equation (8.23), it follows that

$$H^{-1}B{x}_i^{(j)}= \theta_i^{(j)} {x}_i^{(j)} + \gamma_i^{(j)}q_{j+1}.$$

Hence a purified Ritz vector, $(1/\theta_i^{(j)})H^{-1}B{x}_i^{(j)},$ can be cheaply computed by simply updating ${x}_i^{(j)}$ with a multiple of $q_{j+1}$:

$$x_i^{(j)} := {x}_i^{(j)} + \frac{\gamma_i^{(j)}}{\theta_i^{(j)}}q_{j+1}.$$ (240)

This technique was originally presented in [162] as a mechanism for improving the quality of the Ritz vectors, and it was later shown in [340] to have the purifying effect required here. Numerical experience has shown that the updated vector lies almost entirely in the range of $H^{-1} B$ and generally provides a better eigenvector approximation. This scheme is also recommended for use in the indefinite case.