Multiple Eigenvalues.

In theory, we get convergence only to eigenvectors that are represented in the starting vector. Normally this is not of any great concern, since rounding errors will also introduce those directions that were not present at the outset into the computation. However, in one case this is important, namely, when the matrix $A$ has multiple eigenvalues. In that case, we will get only one vector from the multidimensional invariant subspace of this multiple eigenvalue. Note that any vector in the subspace is equally valid: there is no way for this, or any other algorithm, to choose a special vector and each Lanczos run with a different starting vector will yield a new suggestion for an eigenvector to a multiple eigenvalue.

There are two different ways to get a set of linearly independent eigenvectors to a multiple eigenvalue. The first is to restart and run a projected operator on the subspace orthogonal to the converged eigenvector(s), where all the converged eigendirections have been projected away. This corresponds to orthogonalizing the vector $r$ in step (9) of Algorithm 4.6 to all converged eigenvectors. This procedure is repeated as long as new vectors converge; see, e.g., [318]. There is a second, more radical way to deal with possibly multiple eigenvalues: the block Lanczos method. It starts with several, say $p$, starting directions, forming a block $V_1$, and lets $A$ operate on all of $V_j$ in step $j$, to compute a new orthogonal block $V_{j+1}$. The matrix $T$ will be a block-tridiagonal, or more properly band matrix; see the description in §4.6.

In the block Lanczos method, the convergence is governed by the separation of the desired eigenvalue $\lambda_i$ from other $p$ eigenvalues away in the spectrum, say $\lambda_{i+p}$, if we assume the eigenvalues sorted from smallest to largest. However, the degree of the polynomial is $j$, not $jp$, as we would have if we ran single-vector Lanczos for the same number of basis vectors, and this will slow down the convergence in the general case.

Regardless of the above objection, block Lanczos is advantageous for efficiency reasons, whenever computing $Y=AX$ for an $n\times p$ matrix $X$ is much cheaper than computing $y=Ax$ for $p$ vectors, one after the other. This is the case for most machines with cache memories and when the matrices are so large that they need to be stored in secondary storage.