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:
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.
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 .
This level attempts to maintain semi-biorthogonality. It is less expensive in both floating point operations and memory references than full biorthogonality.
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:
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.
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:
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).
The biorthogonality of the st Lanczos vectors
and
to the previous Lanczos vectors is measured by the
quantity