Basic Properties

After iterations, the algorithm has generated the
vectors (7.62).
It will be convenient to introduce the notation

In order to enforce biorthogonality of the next Lanczos vectors, the algorithm involves division by the diagonal entries, , in (7.64). As a result, the algorithm has to be stopped as soon as

occurs. The situation (7.65) is called a

After iterations, in addition to (7.62), the algorithm
has constructed the vectors

The algorithm has a very simple built-in deflation procedure based on the vectors (7.66). In fact, an exact deflation in the right block Krylov sequence at iteration is equivalent to . Therefore, in the algorithm, one checks if is smaller than some suitable deflation tolerance. If yes, the vector is deflated and is reduced by 1. Otherwise, is normalized to become the next right Lanczos vector . Similarly, an exact deflation in the left block Krylov sequence at iteration is equivalent to . In the algorithm, one checks if is smaller than the deflation tolerance. If yes, the vector is deflated and is reduced by 1. Otherwise, is normalized to become the next left Lanczos vector .

The recurrences that are used in the algorithm to generate the
vectors (7.62) and (7.66) can be summarized
compactly as follows:

where is a banded matrix and contains horizontal ``spikes'' above the band of due to deflation of vectors. Similarly,

where the banded part has lower bandwidth and upper bandwidth , and contains horizontal ``spikes'' above the band of due to deflation of vectors.

The entries of the matrices and are not
independent of each other.
More precisely, setting

where is the diagonal matrix given by (7.64). Inserting (7.69) into the definition of in (7.70), we obtain the relation

which shows that consists of the banded part , horizontal spikes due to deflation of vectors above the banded part, and vertical spikes due to deflation of vectors below the banded part.

For example, consider the case of right and left
starting vectors.
Assume that during the first iterations, deflations
of vectors have occurred at iterations , , and
, and deflations of vectors have
occurred at iterations and .
In this case, the matrix
has the following
sparsity structure:

Here, the 's denote potentially nonzero entries within the banded part, ; the 's denote potentially nonzero entries due to the deflations of vectors at iterations , , and ; and the 's denote potentially nonzero entries due to the deflations of vectors at iterations and . Note that the deflations have reduced the initial lower bandwidth to at iteration and the initial upper bandwidth to at iteration .

After iterations of the band Lanczos algorithm,
approximate eigensolutions for the NHEP (7.58)
are obtained via an
oblique projection of the matrix onto the subspace spanned
by the columns of and orthogonal to the subspace spanned
by the columns of .
More precisely, this means that we are seeking approximate
eigenvectors of (7.58) of the form
and that, after inserting this ansatz for
into (7.58),
we multiply the resulting relation from the left by .
This yields the generalized eigenvalue problem

By (7.73), the generalized eigenvalue problem (7.72) is equivalent to the standard eigenvalue problem

We stress that, in the algorithm, we use the formula in (7.70) to obtain the entries of , rather than (7.73).

The band Lanczos algorithm terminates as soon as or is reached. In the case , deflations of vectors have occurred, and thus the right block Krylov sequence (7.60) is exhausted. In the case , deflations of vectors have occurred, and thus the left block Krylov sequence (7.61) is exhausted.

First consider termination due to .
Then, the relation for the
right Lanczos vectors in (7.68) can be rewritten as follows:

represents the oblique projection characterized by and for all in the null space of . Now let and be any of the eigenpairs of , and assume that is normalized so that . Recall that the pair and is used as an approximate eigensolution of . From (7.74), it follows that the residual of this approximate eigensolution can be bounded as follows:

In particular, if only exact deflation is performed, then and (7.76) shows that each eigenvalue of is indeed an eigenvalue of .

Similarly, in the case of termination due to ,
the relation for the left Lanczos vectors in (7.68)
can be rewritten as follows:

In particular, if only exact deflation is performed, then and (7.78) shows that each eigenvalue of is indeed an eigenvalue of and thus of .