Basic Properties

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

$$V_j = \left[ \begin{array}{cccc} v_1 & v_2 & \cdots & v_j ... ...in{array}{cccc} w_1 & w_2 & \cdots & w_j \end{array} \right]$$ (169)

for the matrices whose columns are just the right and left Lanczos vectors (7.62), respectively. The vectors (7.62) are constructed to be biorthogonal. Using the notation (7.63), the biorthogonality can be stated compactly as follows:

$$W_j^T V_j = D_j = {\mathop{\rm diag}\nolimits}\left(\delta_1, \delta_2,\ldots,\delta_j\right).$$ (170)

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

$$\delta_k = w_k^T v_k = 0,\quad \mbox{but}\quad v_k,\; w_k \not=0,$$ (171)

occurs. The situation (7.65) is called a breakdown of the algorithm. While breakdowns can be remedied by incorporating so-called look-ahead into the algorithm, here, for simplicity, we discuss only the band Lanczos algorithm without look-ahead.

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

$$\hat{v}_{j+1},\hat{v}_{j+2},\ldots,\hat{v}_{j+m_c} \quad \mbox{and}\quad \hat{w}_{j+1},\hat{w}_{j+2},\ldots,\hat{w}_{j+p_c}.$$ (172)

The vectors $\hat{v}_{j+1},\hat{v}_{j+2},\ldots,\hat{v}_{j+m_c}$ are the candidates for the next $m_c$ right Lanczos vectors, $v_{j+1},v_{j+2},\ldots,v_{j+m_c}$, and the vectors $\hat{w}_{j+1},\hat{w}_{j+2},\ldots,\hat{w}_{j+p_c}$ are the candidates for the next $p_c$ left Lanczos vectors, $w_{j+1},w_{j+2},\ldots,w_{j+p_c}$. Here, $m_c$ is the number of right starting vectors, $m$, minus the number of deflations in the right block Krylov sequence that have occurred during the first $j$ iterations, and $p_c$ is the number of left starting vectors, $p$, minus the number of deflations in the left block Krylov sequence that have occurred during the first $j$ iterations. The vectors (7.66) are constructed so that they satisfy the biorthogonality relations

$$\begin{array}{rl} W_j^T \hat{v}_{k} &\!\!\! = 0 \quad \mbox{... ... \quad \mbox{for all} \quad k=j+1,j+2,\ldots,j+p_c. \end{array}$$ (173)

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 $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 $m_c$ is reduced by 1. Otherwise, $\hat{v}_{j+1}$ is normalized to become the next right Lanczos vector $v_{j+1}$. Similarly, an exact deflation in the left block Krylov sequence at iteration $j+1$ is equivalent to $\hat{w}_{j+1}=0$. In the algorithm, one checks if $\left\Vert\hat{w}_{j+1}\right\Vert _2$ is smaller than the deflation tolerance. If yes, the vector $\hat{w}_{j+1}$ is deflated and $p_c$ is reduced by 1. Otherwise, $\hat{w}_{j+1}$ is normalized to become the next left Lanczos vector $w_{j+1}$.

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

$$\begin{array}{rl} A V_j &\!\!\! = V_j T_j + \left[ \begin{ar... ..._c} \end{array} \right] + \hat{W}_j^{\rm {(dl)}}. \end{array}$$ (174)

Here, $T_j$ and $\tilde{T}_j$ are $j\times j$ matrices whose entries are chosen so that the biorthogonality conditions (7.64) and (7.67) are satisfied. The matrix $\hat{V}_j^{\rm {(dl)}}$ in (7.68) contains mostly zero columns, together with the $\hat{v}_k$ vectors that have been deflated during the first $j$ iterations. The matrix $\hat{W}_j^{\rm {(dl)}}$ in (7.68) contains mostly zero columns, together with the $\hat{w}_k$ vectors that have been deflated during the first $j$ iterations. We remark that $m-m_c$ is the number of deflated $\hat{v}_k$ vectors and that $p-p_c$ is the number of deflated $\hat{w}_k$ vectors. It turns out that biorthogonality only has to be explicitly enforced among $m_c+p_c+1$ consecutive Lanczos vectors and, once deflation has occurred, against $p-p_c$ fixed earlier left Lanczos vectors, respectively, $m-m_c$ fixed earlier right Lanczos vectors. As a result, the matrices $T_j$ and $\tilde{T}_j$ are ``essentially'' banded. More precisely, $T_j$ has lower bandwidth $m_c+1$ and upper bandwidth $p_c+1$, where the lower bandwidth is reduced by 1 every time a $\hat{v}_{k}$ vector is deflated, and the upper bandwidth is reduced by 1 every time a $\hat{w}_{k}$ vector is deflated. In addition, each deflation of a $\hat{w}_{k}$ vector 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 of a $\hat{w}_{k}$ vector 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)}},$$ (175)

where $T_j^{\rm {(b)}}$ is a banded matrix and $T_j^{\rm {(d)}}$ contains horizontal ``spikes'' above the band of $T_j$ due to deflation of $\hat{w}_{k}$ vectors. Similarly,

$$\tilde{T}_j = \tilde{T}_j^{\rm {(b)}} + \tilde{T}_j^{\rm {(d)}},$$

where the banded part $\tilde{T}_j^{\rm {(b)}}$ has lower bandwidth $p_c+1$ and upper bandwidth $m_c+1$, and $\tilde{T}_j^{\rm {(d)}}$ contains horizontal ``spikes'' above the band of $\tilde{T}_j$ due to deflation of $\hat{v}_{k}$ vectors.

The entries of the matrices $T_j$ and $\tilde{T}_j$ are not independent of each other. More precisely, setting

$$T_j^{\rm (pr)} = T_j + D_j^{-1} \left(\tilde{T}_j^{\rm {(d)... ...= \tilde{T}_j + D_j^{-1} \left(T_j^{\rm {(d)}}\right)^T D_j,$$ (176)

we have

$$T_j^{\rm (pr)} = D_j^{-1} \left(\tilde{T}_j^{\rm (pr)}\right)^T D_j,$$ (177)

where $D_j$ is the diagonal matrix given by (7.64). Inserting (7.69) into the definition of $T_j^{\rm (pr)}$ in (7.70), we obtain the relation

$$T_j^{\rm (pr)} = T_j^{\rm {(b)}} + T_j^{\rm {(d)}} + D_j^{-1} \left(\tilde{T}_j^{\rm {(d)}}\right)^T D_j,$$

which shows that $T_j^{\rm (pr)}$ consists of the banded part $T_j^{\rm {(b)}}$, horizontal spikes due to deflation of $\hat{w}_{k}$ vectors above the banded part, and vertical spikes due to deflation of $\hat{v}_{k}$ vectors below the banded part.

For example, consider the case of $m=3$ right and $p=5$ left starting vectors. Assume that during the first $j=15$ iterations, deflations of $\hat{w}_k$ vectors have occurred at iterations $k=8$, $k=11$, and $k=13$, and deflations of $\hat{v}_k$ vectors have occurred at iterations $k=7$ and $k=12$. In this case, the matrix $T^{(\rm pr)}_{15}$ has the following sparsity structure:

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

Here, the ${*}$'s denote potentially nonzero entries within the banded part, $T_{15}^{\rm {(b)}}$; the ${\tt d}$'s denote potentially nonzero entries due to the deflations of $\hat{w}_k$ vectors at iterations $k=8$, $k=11$, and $k=13$; and the $\tilde{{\tt d}}$'s denote potentially nonzero entries due to the deflations of $\hat{v}_k$ vectors at iterations $k=7$ and $k=12$. Note that the deflations have reduced the initial lower bandwidth $m+1 = 4$ to $m_c+1=2$ at iteration $j=15$ and the initial upper bandwidth $p+1 = 6$ to $p_c+1 = 3$ at iteration $j=15$.

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

$$W_j^T A V_j z_i^{(j)} = \theta_i^{(j)} W_j^T V_j z_i^{(j)},\quad i=1,2,\ldots,j.$$ (178)

Using the biorthogonality relations (7.64) and (7.67), it is easy to verify that the matrix $T_j^{\rm (pr)}$ defined in (7.70) satisfies

$$T_j^{\rm {(pr)}} = \left(W_j^T V_j\right)^{-1} W_j^T A V_j.$$ (179)

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

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

We stress that, in the algorithm, we use the formula in (7.70) to obtain the entries of $T_j^{\rm (pr)}$, rather than (7.73).

The band Lanczos algorithm terminates as soon as $m_c=0$ or $p_c=0$ is reached. In the case $m_c=0$, $m$ deflations of $\hat{v}_k$ vectors have occurred, and thus the right block Krylov sequence (7.60) is exhausted. In the case $p_c=0$, $p$ deflations of $\hat{w}_k$ vectors have occurred, and thus the left block Krylov sequence (7.61) is exhausted.

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

$$A V_j - V_j T_j^{\rm {(pr)}} = P_j \hat{V}_j^{\rm {(dl)}}.$$ (180)

Here, the matrix

$$P_j = I - V_j D_j^{-1} W_j^T,\quad \mbox{where}\quad D_j = W_j^T V_j,$$ (181)

represents the oblique projection characterized by $P_j V_j = 0$ and $P_j x = x$ for all $x$ in the null space of $W_j^T$. 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 $\left\Vert z_i^{(j)}\right\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$. From (7.74), it follows that the residual of this approximate eigensolution can be bounded as follows:

$$\left\Vert A x_i^{(j)} - \theta_i^{(j)} x_i^{(j)} \right\Ver... ...rt _2 \cdot \left\Vert \hat{V}_j^{\rm {(dl)}} \right\Vert _2.$$ (182)

In particular, if only exact deflation is performed, then $\hat{V}_j^{\rm {(dl)}} = 0$ and (7.76) shows that each eigenvalue $\theta_i^{(j)}$ of $T_j^{\rm {(pr)}}$ is indeed an eigenvalue of $A$.

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

$$A^T W_j - W_j \tilde{T}_j^{\rm {(pr)}} = P_j^T \hat{W}_j^{\rm {(dl)}}.$$ (183)

Here, $P_j$ is again the matrix defined in (7.75). Now let $\theta_i^{(j)}$ and $\tilde{z}_i^{(j)}$ be any of the eigenpairs of $(T_j^{\rm {(pr)}})^T$, and assume that $\tilde{z}_i^{(j)}$ is normalized such that $\Vert D_j^{-1} \tilde{z}_i^{(j)}\Vert _2 = 1$. Note that the complex conjugate of $\tilde{z}_i^{(j)}$ is a left eigenvector of $T_j^{\rm {(pr)}}$. The pair $\theta_i^{(j)}$ and $y_i^{(j)} = W_j D_j^{-1} \tilde{z}_i^{(j)}$ then represents an approximate eigensolution of $A^T$. From (7.77), it follows that the residual of this approximate eigensolution can be bounded as follows:

$$\left\Vert A^T y_i^{(j)} - \theta_i^{(j)} y_i^{(j)} \right\V... ...rt _2 \cdot \left\Vert \hat{W}_j^{\rm {(dl)}} \right\Vert _2.$$ (184)

In particular, if only exact deflation is performed, then $\hat{W}_j^{\rm {(dl)}} = 0$ and (7.78) shows that each eigenvalue $\theta_i^{(j)}$ of $T_j^{\rm {(pr)}}$ is indeed an eigenvalue of $A^T$ and thus of $A$.