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:

The vectors and are called

and

The computed quantities satisfy the governing relations, called

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,

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,

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

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

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 forApplying 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.