Next: Convergence Properties Up: Lanczos Method   Z. Bai Previous: Lanczos Method   Z. Bai   Contents   Index

## Algorithm

The non-Hermitian Lanczos method as presented in Algorithm 7.13 below is a two-sided iterative algorithm with starting vectors and . It can be viewed as biorthogonalizing, via a two-sided Gram-Schmidt procedure, the two Krylov sequences

The two sequences of vectors and are generated using the three-term recurrences:
 (139) (140)

The vectors and are called Lanczos vectors, span and , respectively, and are biorthogonal, namely, if and . In matrix notation, at the th step, the Lanczos method generates two matrices and :

and

The computed quantities satisfy the governing relations, called Lanczos factorizations:
 (141) (142) (143)

In addition, and . The relation (7.37) shows that the Lanczos vectors (bases) are biorthonormal. But note that neither nor is unitary. In the Lanczos bases, the matrix is represented by a non-Hermitian tridiagonal matrix,
 (144)

At any step , we may compute eigensolutions of ,

Eigenvalues of are approximated by the eigenvalues of , which are called Ritz values.

To each Ritz value there correspond right and left Ritz vectors,

 (145)

The convergence of the Ritz values and vectors to eigenvalues and eigenvectors of the original matrix can be evaluated by comparing the norms of the residuals
 (146) (147)

to the norms of and , respectively. Moreover, by equation (7.35), the right residual vector becomes
 (148)

and by equation (7.36), the left residual vector becomes
 (149)

Therefore, as in the Hermitian case (see §4.4), the residual norms are available without explicitly computing the Ritz vectors and , though and are unavailable. See §7.8.2 for a more detailed discussion of this topic.

We will now comment on certain steps of Algorithm 7.13:

(1)
The initial starting vectors and are best selected by the user to embody any available knowledge concerning 's wanted eigenvectors. In the absence of such knowledge, one can choose with randomly distributed entries and let .

(2), (3), (18), (19)
The matrix-vector multiplication routines to multiply and by an arbitrary vector are required in these steps. This is usually the computational bottleneck. See the discussion of convergence properties below for implementation notes in the shift-and-invert case.

(8)
This is one of two cases in which the method may break down. In fact, this is a desirable breakdown. If is null, then the Lanczos vectors span a (right) invariant subspace of ; each Ritz value and corresponding right Ritz vector is an exact eigenvalue and eigenvector of . The Lanczos algorithm may be continued if necessary by taking as any vector such that and setting . Similar actions can be taken when or both and vanish.

In practice, an exact null vector is rare. It does happen that the norms of and/or are tiny. A tolerance value to detect a tiny compared to or a tiny compared to should be given. A default tolerance value is a small multiple of , the machine precision.

(10)
If before either or vanishes, the method has an essential breakdown. In most cases we may continue finding new vectors in the Krylov subspaces and for some integer , and add a block outside the three diagonals of ; this so-called look-ahead procedure is described in [178] and implemented in QMRPACK (see §7.8.3 below). If, however, our starting vectors and have different minimal polynomials (or, say, and are composites of different set of eigenvectors), even this does not help, and we have a mismatch, also called incurable breakdown. See [354] for a further discussion. A different treatment of the breakdown is discussed in §7.9.

In practice, exact breakdown is rare. Near breakdowns occur more often; i.e., is nonzero but extremely small in absolute value. Near breakdowns cause stagnation and instability. Any criterion for detecting a near breakdown either must stop too early in some situations or stops too late in other cases. A reasonable compromise criterion for detecting near breakdowns in an eigenvalue problem is to stop if .

(15)
The cost of computing eigendecomposition of the tridiagonal matrix by the QR algorithm (see §7.3) is approximately floating point operations per iteration, and the cumulative cost for steps 1 to is floating point operations. Solving the eigenproblem periodically, say at every 10 steps, reduces this cost.

No stable algorithm has been found for an eigenvalue problem that approximates the eigenvalues of a general tridiagonal in floating point operations, though recently conditionally stable algorithms such as [94,189] have been proposed. No software implementation of the Lanczos algorithm known to the authors employs a fast conditionally stable eigensolver.

(16)
Computation halts once bases and have been determined so that eigenvalues of  (7.38) approximate all the desired eigenvalues of with sufficiently small residuals, which are calculated according to the equations (7.42) and (7.43). Convergence properties are discussed in more detail in §7.8.2.

If there is no re-biorthogonalization (see [105]), then in finite precision arithmetic after a Ritz value converges to an eigenvalue of , copies of this Ritz value will appear at later Lanczos steps. For example, a cluster of Ritz values of the reduced tridiagonal matrix, , may approximate a single eigenvalue of the original matrix . A spurious value [93] is a simple Ritz value that is also an eigenvalue of the matrix of order obtained by deleting the first row and column from . Such spurious values should be discarded from consideration. Eigenvalues of which are not spurious are identified as approximations to eigenvalues of the original matrix and are tested for convergence.

(17)
As in the Hermitian case, in the presence of finite precision arithmetic, the biorthogonality of computed Lanczos vectors and deteriorates. One may use the two-sided modified Gram-Schmidt (TSMGS) process [354] to re-biorthogonalize the st Lanczos vectors;


for

end for


Applying the TSMGS process at each step is very costly and becomes a computational bottleneck. In [105], an efficient alternative scheme is proposed. This topic is revisited in §7.9.

Next: Convergence Properties Up: Lanczos Method   Z. Bai Previous: Lanczos Method   Z. Bai   Contents   Index
Susan Blackford 2000-11-20