Next: Storage Requirements and Floating Up: Block Lanczos Methods   Previous: Basic Algorithm   Contents   Index

## 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.
There are four levels of implementation of ABLE:
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.

Subsections

Next: Storage Requirements and Floating Up: Block Lanczos Methods   Previous: Basic Algorithm   Contents   Index
Susan Blackford 2000-11-20