Algorithm

- (a)
- If one wants a few of the eigenvalues of which are largest
in magnitude, and if the matrix is nonsingular,
we may multiply by to obtain

The matrix is symmetric with respect to or . - (b)
- If one wants a few of the eigenvalues closest to a given value
, we apply the SI
to obtain

In particular, if the smallest eigenvalues in magnitude are desired, one could choose the shift value . Note that the matrix is symmetric with respect to or .

We will focus on case (b) in the rest of this section
and write the transformed problem as

where

Note that the eigenvalues of may be complex even when and are real, so it may be necessary to use a value of which is complex. The Lanczos recursion may still be implemented using real arithmetic even if a complex shift is used; see [362].

A symmetric indefinite Lanczos algorithm template is presented in
Algorithm 8.4.
The generated Lanczos vectors and scalars
satisfy the
following governing equations:

The Lanczos vectors
are orthogonal, i.e.,

and are normalized to have unit Euclidean norm, i.e., .

The reduced eigenvalue problem is

It inherits the same numerical difficulties as the original problem. For example, Ritz value could be complex, and even defective. In other words, it may belong to a nondiagonal Jordan block of .

Once
are computed, the right
and left Ritz vectors are defined as

respectively. The quantities are referred to as

The (right) residual vectors
corresponding to the Ritz pairs
are

Note that the last equality in (8.23) is obtained by multiplying equation (8.22) on the right by and the definition of . Note that the left residual vectors are related to the right residual vectors by It follows that

and

Note that the vector is directly available in every iteration of the symmetric indefinite Lanczos algorithm. No extra call on is necessary. Therefore, one of the attractive features of the Lanczos algorithm is that the residual vectors can be calculated without explicitly computing Ritz vectors and .

We now comment on some steps of Algorithm 8.4:

**(1)**- The ideal initial vector is one which is a linear combination of the
eigenvectors corresponding to the desired eigenvalues. If an approximation of
such a vector is
not available, then a random vector may be used. The initial vector
is often preprocessed by multiplying it by . This preprocessing step
was suggested in [161] and is essential when is singular; see
§8.6.4 for details.
**(4) and (15)**- The matrix-vector multiplication should be
performed by a user-provided subroutine which can take advantage of the
data structure of the matrix .
**(7)**- The linear system of equations must be solved for .
Let

be the sparse LDL factorization (see §10.3) computed before the for-loop. Then the vector can be efficiently computed in three steps:`solve for`

solve for

solve for **(12)**- When , it
indicates that all of the eigenvalues of the pencil
are also the eigenvalues of , and the columns of
span an invariant subspace. One can either exit the algorithm or
continue the algorithm by setting
the value of to zero and selecting to be a random vector
which is orthogonal to the columns of .
**(13)**- In finite precision arithmetic, the vectors
are no longer orthogonal. The schemes for reorthogonalization
which are discussed for the standard symmetric Lanczos procedure may be
extended to the symmetric indefinite algorithm; see §4.4
for details.
**(14)**- In the symmetric Lanczos algorithm (see §4.4),
the Lanczos vectors are scaled to be orthonormal, .
However, in the symmetric indefinite algorithm, the vectors are scaled so that

There are two reasons for the change in scaling, both of which have to do with the indefiniteness of . The first reason is that even when and are real, scaling the Lanczos vectors so that may involve complex arithmetic. (By keeping track of the sign of it is possible to avoid complex arithmetic but still use as a norm. However, this algorithm is less stable.) The second reason is that when is indefinite, not every subspace has a -orthonormal basis, and even if it does, it may be highly ill-conditioned [417,20]. The choice of scaling does not remedy the possibility of an ill-conditioned basis of Lanczos vectors. However, it does provide a convenient means of detecting when the basis is becoming ill-conditioned, specifically, a tiny value of [357]. **(17)**- If
, the Lanczos procedure suffers a
breakdown similar to the breakdown which occurs in the non-Hermitian
Lanczos procedure; see §7.8.
The same remedies developed for the
non-Hermitian Lanczos procedure, such as look-ahead
[364,178] and adaptive blocking [29,298], can be
employed.
**(19)**- The approximate eigenvalues of the matrix pencil
are determined
by solving the reduced generalized eigenvalue problem

There are several algorithms available for solving this problem. If is small, one could apply the standard QZ algorithm to or the QR algorithm to . However, neither of these algorithms take advantage of the structure of . A good survey of algorithms which exploit the symmetry of is contained in [357], and some more recent work can be found in [406,407].For even moderate values of (e.g., ), solving the reduced problem becomes computationally significant. For long Lanczos runs, it is recommended to solve the reduced problem periodically, perhaps once in every five or ten Lanczos iterations.

A proper stopping criterion for the inner loop of the symmetric indefinite Lanczos method is

where is a user-given tolerance value. Note that is available at the end of a Lanczos run, and its Euclidean norm can be computed at the cost of one dot product. No extra call on is necessary for that term. An elaborate testing procedure for the convergence is discussed in the following §8.6.3. **(21)**- Compute the approximate eigenvectors only when the
corresponding Ritz values have converged according to the test described below.