Lanczos Method in GEMV Form

At each restart in Algorithm 4.7 we have a $k$-step Lanczos factorization

$$AV_k = V_k T_k + r_k e_k^{\ast}$$

or, for $k=0$ a starting vector $r_0$. Algorithm 4.8 gives a template for applying $p$ additional Lanczos steps to extend this to an $m$-step Lanczos factorization

$$AV_m = V_m T_m + r_m e_m^{\ast}.$$

We will now describe some implementation details, referring to the respective phases in Algorithm 4.8.

(2)

If started from scratch ($k=0$) take $r_0=v$ as a starting vector. Ideally, for eigenvalue calculations, one should attempt to construct a $v$ that is dominant in eigenvector directions of interest. In the absence of any other considerations, a random vector is a reasonable choice.

(3)

Normalize $r$ to get the new basis vector $v_{j}$. The norm $\beta_{j-1} = \Vert r \Vert$ has already been computed at step (7) for the previous $j$.

(5)

This is the Lanczos three-term recurrence step to orthogonalize $r$ with respect to the two most recent columns of $V_j$. It is organized in modified Gram-Schmidt form.

(7)

The sequence of statements in this if clause assure that the new residual direction $r$ is numerically orthogonal to the previously computed directions, i.e., to all of the columns of $V_{j}$. The parameter $\rho$ must be specified ( $0 \le \rho < \infty$). The test asks the question, ``Is $r = Av_{j}$ nearly in the space that already has been constructed?" The ratio $\Vert r\Vert/ \sqrt{ \alpha_{j}^2 + \beta_{j-1}^2 } = \tan \theta$, where $\theta$ is the angle that the vector $r$ makes with the range space of $V_{j}$. A larger value of $\rho$ is a more stringent orthogonality requirement. With $\rho = 0$, the algorithm reverts to the standard Lanczos process without reorthogonalization. One step of this correction may not be sufficient and it should be implemented as an iteration with the test for subsequent corrections being $\Vert r\Vert < \rho \Vert s \Vert$; see the discussion in [96]. If a suitable $r$ has not been generated after a fixed number of attempts (say five), then $\beta_{j}$ should be set to zero and a randomly generated vector should be orthogonalized against the basis $V_j$ and put in place of $r$ to continue the factorization. We suggest setting $\rho = 1$.

It is well known that the classical three-term Lanczos scheme will fail to produce orthogonal vectors precisely when a Ritz value (approximate eigenvalue) converges to an eigenvalue of $A$. To remedy this, we have included an iterative refinement technique which maintains orthogonality to full working precision at a very reasonable cost. The special situation imposed by implicit restart makes this modification essential for obtaining accurate eigenvalues and numerically orthogonal eigenvectors. The implicit restart mechanism will be less effective and may even fail if numerical orthogonality is not maintained.