Basic Properties

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

$$V_j^{\ast} V_j = I_j,\quad \mbox{where}\quad V_j = \left[ \begin{array}{cccc} v_1 & v_2 & \cdots & v_j \end{array} \right].$$ (38)

Here, $I_j$ denotes the $j\times j$ identity matrix. In addition to (4.28), the algorithm has constructed the vectors

$$\hat{v}_{j+1},\hat{v}_{j+2},\ldots,\hat{v}_{j+p_c},$$ (39)

which are the candidates for the next $p_c$ Lanczos vectors, $v_{j+1},v_{j+2},\ldots,v_{j+p_c}$. Here, $p_c$ is the number of starting vectors, $p$, minus the number of deflations that have occurred during the first $j$ iterations. The vectors (4.30) are constructed so that they satisfy the orthogonality relations

$$V_j^{\ast} \hat{v}_{k} = 0 \quad \mbox{for all} \quad k=j+1,j+2,\ldots,j+p_c.$$ (40)

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 $j+1$ is equivalent to $\hat{v}_{j+1}=0$. Therefore, in the algorithm, one checks if $\left\Vert\hat{v}_{j+1}\right\Vert _2$ is smaller than some suitable deflation tolerance. If yes, the vector $\hat{v}_{j+1}$ is deflated and $p_c$ is reduced by 1. Otherwise, $\hat{v}_{j+1}$ is normalized to become the next Lanczos vector $v_{j+1}$.

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

$$A V_j = V_j T_j + \left[ \begin{array}{ccccccc} 0 & \cdots ... ...hat{v}_{j+p_c} \end{array} \right] + \hat{V}_j^{\rm {(dl)}}.$$ (41)

Here, $T_j$ is a $j\times j$ matrix whose entries are chosen so that the orthogonality conditions (4.29) and (4.31) are satisfied. The matrix $\hat{V}_j^{\rm {(dl)}}$ in (4.32) contains mostly zero columns, together with the unnormalized vectors that have been deflated during the first $j$ iterations. Recall that $p-p_c$ is the number of deflated vectors.

It turns out that orthogonality only has to be explicitly enforced among $2p_c+1$ consecutive Lanczos vectors and, once deflation has occurred, against $p-p_c$ fixed earlier vectors. As a result, the matrix $T_j$ is ``essentially'' banded with bandwidth $2p_c+1$, where the bandwidth is reduced by 2 every time a deflation occurs. In addition, each inexact deflation causes $T_j$ 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 $k - p_c(k)$, where $k$ is the number of the iteration at which the deflation has occurred and $p_c(k)$ is the corresponding value of $p_c$ at that iteration. The matrix $T_j$ can thus be written as

$$T_j = T_j^{\rm {(b)}} + T_j^{\rm {(d)}},$$ (42)

where $T_j^{\rm {(b)}}$ is a banded matrix and $T_j^{\rm {(d)}}$ contains the horizontal ``spikes'' outside the band of $T_j$ due to deflation. In particular, if no inexact deflation has occurred, then $T_j^{\rm {(d)}}$ is the zero matrix. Finally, we note that the banded part $T_j^{\rm {(b)}}$ of $T_j$ is a Hermitian matrix.

For example, consider the case of $p=5$ starting vectors and assume that during the first $j=15$ iterations, deflations have occurred at steps $k=8$, $k=11$, and $k=13$. These three deflations correspond to deleting the vectors $A b_3$, $A^2 b_2$, and $A^3 b_1$, as well as the following $A$-multiples of these three vectors, from the block Krylov sequence (4.27). In this case, the matrix $T_{15}=T_{15}^{\rm {(b)}} + T_{15}^{\rm {(d)}}$ has the following sparsity structure:

$$T_{15} = %%\footnotesize{ \left[ \begin{array}{ccccccccccccc... ... \\ & & & & & & & & & & & &{*}&{*}&{*} \end{array} \right].$$ (43)

Here, the ${*}$'s denote potentially nonzero entries within the banded part, $T_{15}^{\rm {(b)}}$, and the ${\tt d}$'s denote potentially nonzero entries of $T_{15}^{\rm {(d)}}$ due to the deflations at iterations $k=8$, $k=11$, and $k=13$. Note that the three deflations have reduced the initial bandwidth $2p+1=11$ to $2p_c+1=5$ at iteration $j=15$.

After $j$ iterations of the band Lanczos algorithm, approximate eigensolutions for the Hermitian eigenvalue problem (4.25) are obtained by computing eigensolutions of $T_j^{\rm {(pr)}}$,

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

Here, $T_j^{\rm {(pr)}}$ is the projection of $A$ onto the space spanned by the Lanczos basis matrix $V_j$, i.e.,

$$T_j^{\rm {(pr)}} = V_j^{\ast} A V_j.$$ (44)

Each value $\theta_i^{(j)}$ and its Ritz vector, $x_i^{(j)} = V_j z_i^{(j)}$, yield an approximate eigenpair of $A$. Of course, the matrix $T_j^{\rm {(pr)}}$ is not computed via its definition (4.35). Instead, we use the formula

$$T_j^{\rm {(pr)}} = T_j + \left(T_j^{\rm {(d)}}\right)^{\ast}.$$ (45)

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

$$T_j^{\rm {(pr)}} = V_j^{\ast} A V_j = T_j + S_j, \quad \mbox{where} \quad S_j = V_j^{\ast} \hat{V}_j^{\rm {(dl)}}.$$ (46)

Since the matrices $T_j^{\rm {(pr)}}$ and $T_j^{\rm {(b)}}$ are both Hermitian, it follows from (4.33) that $S_j = (T_j^{\rm {(d)}})^{\ast}$ in (4.37). Thus (4.37) reduces to (4.36).

For example, for $T_{15}$ in (4.34) the associated matrix $T_{15}^{(\rm pr)} = T_{15} + (T_{15}^{\rm {(d)}})^{\ast}$ is of the form

$$T_{15}^{\rm {(pr)}} = %%\footnotesize{ \left[ \begin{array}{... ... & &\overline{{\tt d}}& & &{*}&{*}&{*} \end{array} \right].$$ (47)

Here, the $\overline{{\tt d}}$'s below the banded part were obtained by conjugating and transposing the corresponding entries above the banded part in (4.34). We remark that, in (4.38), the entries ${\tt d}$ and $\overline{{\tt d}}$ outside the banded part are usually small. More precisely, if the deflation criterion (4.42) below is used, then the absolute values of all ${\tt d}$'s and $\overline{{\tt d}}$'s is bounded by the deflation tolerance ${\tt dtol}$. Even though these entries are small, setting them to zero would introduce unnecessary errors. Indeed, the projection property (4.35) for $T_{j}^{\rm {(pr)}}$ holds true only if all entries ${\tt d}$ and $\overline{{\tt d}}$ outside the banded part are included in $T_{j}^{\rm {(pr)}}$.

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

$$A V_j = V_j T_j + \hat{V}_j^{\rm {(dl)}}.$$ (48)

Using (4.37), we can rewrite (4.39) as follows:

$$A V_j - V_j T_j^{\rm {(pr)}} = \left(I - V_j V_j^{\ast} \right) \hat{V}_j^{\rm {(dl)}}.$$ (49)

Now let $\theta_i^{(j)}$ and $z_i^{(j)}$ be any of the eigenpairs of $T_j^{\rm {(pr)}}$, and assume that $z_i^{(j)}$ is normalized so that $\Vert z_i^{(j)}\Vert _2 = 1$. Recall that the pair $\theta_i^{(j)}$ and $x_i^{(j)} = V_j z_i^{(j)}$ is used as an approximate eigensolution of $A$. By multiplying (4.40) from the right by $z_i^{(j)}$ and taking norms, it follows that the residual of the approximate eigensolution $\theta_i^{(j)}$ and $x_i^{(j)}$ can be bounded as follows:

$$\left\Vert A x_i^{(j)} - \theta_i^{(j)} x_i^{(j)} \right\Ver... ...ert _2 \leq \left\Vert \hat{V}_j^{\rm {(dl)}} \right\Vert _2.$$ (50)

In particular, if only exact deflation is performed, then $\hat{V}_j^{\rm {(dl)}} = 0$ and (4.41) shows that each eigenvalue $\theta_i^{(j)}$ of $T_j^{\rm {(pr)}}$ is indeed an eigenvalue of $A$. For general deflation, $\hat{V}_j^{\rm {(dl)}}\not=0$, however, $\Vert \hat{V}_j^{\rm {(dl)}} \Vert _2$ is of the order of the deflation tolerance. More precisely, if the deflation check (4.42) below is used, then

$$\left\Vert \hat{V}_j^{\rm {(dl)}} \right\Vert _2 \leq \sqrt{p} \; {\tt dtol},$$

where ${\tt dtol}$ denotes the deflation tolerance.