Basic Properties

After the first iterations, the band Lanczos algorithm has
generated the first Lanczos vectors (4.28).
These vectors are constructed to be orthonormal:

which are the candidates for the next Lanczos vectors, . Here, is the number of starting vectors, , minus the number of deflations that have occurred during the first iterations. The vectors (4.30) are constructed so that they satisfy the orthogonality relations

The band Lanczos algorithm has a very simple built-in deflation procedure based on the vectors (4.30). In fact, an exact deflation 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 Lanczos vector .

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

It turns out that orthogonality only has to be explicitly enforced
among consecutive Lanczos vectors and, once deflation has
occurred, against fixed earlier vectors.
As a result, the matrix is ``essentially'' banded with
bandwidth , where the bandwidth is reduced by 2 every time a
deflation occurs.
In addition, each inexact deflation causes to have nonzero elements
in a fixed row outside and to the right of the banded part.
More precisely, the row index of each such row caused by deflation
is given by , where is the number of
the iteration at which the deflation has occurred and is the
corresponding value of at that iteration.
The matrix can thus be written as

For example, consider the case of starting vectors and
assume that during the first iterations, deflations
have occurred at steps , , and .
These three deflations correspond to deleting the vectors ,
, and , as well as the following -multiples
of these three vectors, from the block Krylov sequence (4.27).
In this case, the matrix
has the following sparsity structure:

After iterations of the band Lanczos algorithm,
approximate eigensolutions for the Hermitian
eigenvalue problem (4.25) are obtained by
computing eigensolutions of
,

Here, is the projection of onto the space spanned by the Lanczos basis matrix , i.e.,

Each value and its Ritz vector, , yield an approximate eigenpair of . Of course, the matrix is not computed via its definition (4.35). Instead, we use the formula

By (4.36), we only have to conjugate and transpose the part of outside its banded part and add it to in order to obtain . To show that (4.36) indeed holds true, note that by multiplying (4.32) from the left by and by using the orthogonality relations (4.29) and (4.31), we get

Since the matrices and are both Hermitian, it follows from (4.33) that in (4.37). Thus (4.37) reduces to (4.36).

For example, for in (4.34) the associated
matrix
is of the form

Finally, we note that the band Lanczos
algorithm terminates as soon as is reached.
This means that deflations have occurred, and thus the
block Krylov sequence is exhausted.
At termination due to , the relation (4.32)
for the Lanczos vectors reduces to

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 . By multiplying (4.40) from the right by and taking norms, it follows that the residual of the approximate eigensolution and can be bounded as follows:

In particular, if only exact deflation is performed, then and (4.41) shows that each eigenvalue of is indeed an eigenvalue of . For general deflation, , however, is of the order of the deflation tolerance. More precisely, if the deflation check (4.42) below is used, then

where denotes the deflation tolerance.