An Adaptively Blocked Lanczos Method

Algorithm 7.14 breaks down if
is singular.
Moreover, the computed Ritz triplets can converge slowly due to
either the loss of biorthogonality among the computed
Lanczos vectors and or a block size that is
smaller than the size of the cluster of the desired eigenvalues.
ABLE attempts to avoid breakdowns and
eliminates these causes of slow convergence by
adaptively changing the block size and maintaining the
*full biorthogonality* of the Lanczos vectors,
i.e.,
,
or *semi-biorthogonality*,
i.e.,
.

Algorithm 7.15 is a pseudocode for ABLE. The method can be executed in different increasingly complex levels indicated by the following logical parameters:

*fullbo*- uses the two-sided Gram-Schmidt process to
maintain full biorthogonality at each Lanczos step.
*semibo*- monitors the loss of biorthogonality and
corrects the loss of biorthogonality at certain steps.
*treatbd*- cures the breakdown by increasing the block size.
*group*- adapts the block size to the order of a cluster of converged Ritz values.

*Level 1:*- All logical flags are
`false (F)`.This is the most simple block Lanczos algorithm as in Algorithm 7.14. Essentially, the three-term recurrences (7.50) and (7.51) are used and it does not store the computed Lanczos vectors. Only eigenvalues are computed. The user specifies the parameter

`tolbd`for detecting breakdown. The default value for`tolbd`is , where denotes the machine precision. *Level 2:**fullbo*=`true (T)`and other logical flags are`false (F)`.This version maintains full biorthogonality. Each new pair of Lanczos vectors computed by the three-term recurrences is re-biorthogonalized against all previous Lanczos vectors by TSMGS. Eigentriplets are computed for Levels .

*Level 3:**semibo*=`true (T)`and other logical flags are`false (F)`.This level attempts to maintain semi-biorthogonality. It is less expensive in both floating point operations and memory references than full biorthogonality.

*Level 4:**fullbo*=`true (T)`or*semibo*=`true (T)`and*treatbd*=`true (T)`and/or*group*=`true (T)`.This version attempts to cure breakdowns by increasing the block size and/or by adapting the block size to be at least the order of any detected cluster of converged Ritz values. The user specifies the parameters

`tolbd`and`tolcl`for declaring breakdown and/or grouping a cluster of Ritz values. The default values for`tolcl`and`tolbd`are .

The user may select an implementation of ABLE with either full
biorthogonality (Level 2) or semi-biorthogonality (Level 3), but not both.
Level 4 is implemented on top
of Levels 2 or 3 (full or semi-biorthogonality).
The default values for the logical
flags are all `true` except *fullbo* = `false`.

At Level 1, after a Ritz value converges to an eigenvalue of , copies of this Ritz value 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 heuristic device to detect the spurious Ritz values is proposed in [93] and discussed in §7.8. Such phenomena are not anticipated in the higher levels of ABLE.

We now comment on some steps of Algorithm 7.15:

**(1)**- The comment on step (1) of Algorithm 7.14 applies here as well.
**(2), (3), (35), (36)**- The comment on steps (2), (3) and (20), (21) of Algorithm 7.14
applies here equally well.

**(6), (7)**- The following step for maintaining local
biorthogonality with the block vectors and may be
inserted after step (7):

**(10)**- If or is rank deficient, then and
are biorthogonalized in place against the previous Lanczos vectors
and
using TSMGS.
**(14)**- If the smallest singular value of
is less
than the prescribed tolerance value
`tolbd`, the*breakdown*flag is switched on. denotes the number of the singular values less than`tolbd`. If a breakdown occurs and no treatment is specified by the user (i.e.,*treatbd*=`false`), then the method fails. **(18)**- The order, , of the largest group of clustered values from
converged Ritz values
is determined in this step.
Two Ritz values
and
are regarded as clustered if
,
where
`tolcl`is the user-prescribed tolerance. **(21)**- If breakdown occurs or
if the order of a cluster of
converged Ritz values exceeds the current block size,
,
and can be augmented:

such that is numerically nonsingular, where and are , is determined by , where is the block size before argument and is the prescribed maximum block size. The new block size is . TSMGS is then invoked to biorthogonalize and against previous Lanczos vectors stored in and . This is the so-called adaptive blocking scheme.No feasible method is known to select and that are guaranteed to lift the smallest singular values of above

`tolbd`, except in the case of`tolbd`= 0, i.e., the exact breakdown. One may choose and as random vectors. **(28), (29)**- If semi-biorthogonality is maintained, we solve
the eigenproblem of after each re-biorthogonalization.
The formulas (7.56) and (7.57) can be used to detect convergence. Since we expect too many steps in the Lanczos iteration, at Level 1, we use the following convergence test:

At the higher levels we may use the semiquadratic convergence test:

where

defines the gap between and other Ritz values. Specifically, . In the blocked case, the gap is defined between the clusters.In [29] it is shown that under mild conditions, for a Ritz value , there is an eigenvalue of , such that is proportional to the product of the condition number and the quantity . However, for ill-posed problems (i.e., large condition number), small residuals (backward errors) do not imply high eigenvalue accuracy (small forward error). In this case, the above semiquadratic convergence criterion is optimistic. In any case, the right and left eigenvectors can be used to approximate eigenvalue condition numbers. This detects ill-conditioning in an eigenvalue problem (see §7.13).

**(30)**- If full biorthogonality is required (Level 2), simply use the TSMGS
procedure (see (10))
to biorthogonalize and against all previous
Lanczos vectors stored in and . If
semi-biorthogonality is required (Level 3), the loss of biorthogonality
is monitored and, if necessary, TSMGS is invoked to maintain
semi-biorthogonality.
The biorthogonality of the st Lanczos vectors and to the previous Lanczos vectors is measured by the quantity

An efficient procedure was developed in [29] to efficiently simulate this quantity at cost. **(40)**- The comment to step (25) of Algorithm 7.14 also applies here.