Relationship to Symmetric Lanczos.

From equations (6.7), (6.8), and (6.9), we have

$$A^{\ast} A V_k = V_k B^*_k B_k + \alpha_k \beta_{k}v_{k+1}e^*_k.$$

We note that $B^*_k B_k$ is symmetric and tridiagonal, since $B_k$ is bidiagonal. Comparing to equation (4.10), we see that Algorithm 6.1 computes the same information as Lanczos (Algorithm 4.6) applied to the Hermitian matrix $A^{\ast} A$. Conversely, if we apply Lanczos to $A^* A$ to get a tridiagonal matrix $T_k = B^*_k B_k$, then $B_k$ can be obtained by taking the upper triangular Cholesky factor of $T_k$.

Similarly, one gets

$$AA^* U_k = U_k B_k B_k^* + \beta_k (A v_{k+1}) e_k^*.$$

Again, $B_k B_k^*$ is symmetric and tridiagonal. So again comparing to equation (4.10), we see that Algorithm 6.1 computes the same information as Lanczos (Algorithm 4.6) applied to the Hermitian matrix $AA^*$. Conversely, if we apply Lanczos to $AA^*$ to get a tridiagonal matrix $T_k = B_k B_k^*$, then $B_k$ can be obtained by taking the upper triangular Cholesky factor $B'$ of $JT_kJ$, where $J$ is the identity matrix with its columns in reverse order (so that $JT_kJ$ is gotten by reversing the order of the rows and then the columns of $T_k$), and then $B_k = JB'J$.

Finally, suppose one applies Lanczos (Algorithm 4.6) to $H(A)$ with the special starting vector

$$z_1 = \bmat{c} 0 \\ v_1 \emat$$

to generate the Lanczos vectors $z_2, z_3,\ldots.$ The first step of Algorithm 4.6 yields

$$\begin{eqnarray*} % latex2html id marker 21028r & = & H(A) z_1 = \bmat{c} Av_1... ... \ as\ computed\ in\ line\ (5) \ of\ Algorithm~\ref{gklmethod}.} \end{eqnarray*}$$

The next step of Algorithm 4.6 yields

$$\begin{eqnarray*} % latex2html id marker 21038r & = & H(A) z_2 = \bmat{c} 0 \\... ...s \ as\ computed\ in\ line\ (8)\ of\ Algorithm~\ref{gklmethod}.} \end{eqnarray*}$$

Continuing in this fashion, we see that two steps of Algorithm 4.6 compute the same information as one step of Algorithm 6.1:

$$z_{2i-1} = \bmat{c} 0 \\ v_i \emat \; \; {\rm and} \; \; z_{2i} = \bmat{c} u_i \\ 0 \emat.$$

However, Algorithm 4.6 does twice as many matrix-vectors multiplications by $A$ and $A^*$ as Algorithm 6.1 (half of them by zero vectors), so that Algorithm 6.1 will generally use half the time and space. Conversely, if Lanczos is applied to $H(A)$ to obtain a tridiagonal matrix $T_k$, then $T_k$ will have zeros on its diagonal, and the off-diagonal entries will be identical to the nonzero entries of $B_k$ (notation from equation (6.4)):

$$T_{2k} = \bmat{ccccccc} 0 & \alpha_1 & & & & & \\ \alpha_1... ... \ddots & \ddots & \alpha_k \\ & & & & & \alpha_k & 0 \emat.$$

Because of these equivalences, all the algorithmic variations and convergence properties of Lanczos from §4.4 apply to Algorithm 6.1.