Previous: The Lanczos Connection
Up: Remaining topics
Next: Reduced System Preconditioning
Previous Page: The Lanczos Connection
Next Page: Reduced System Preconditioning

Block Iterative Methods

The methods discussed so far are all subspace methods, that is, in every iteration they extend the dimension of the subspace generated. In fact, they generate an orthogonal basis for this subspace, by orthogonalizing the newly generated vector with respect to the previous basis vectors.

However, in the case of nonsymmetric coefficient matrices the newly generated vector may be almost linearly dependent on the existing basis. To prevent break-down or severe numerical error in such instances, methods have been proposed that perform a look-ahead step (see Freund, Gutknecht and Nachtigal [99], Parlett, Taylor and Liu [168], and Freund and Nachtigal [100]).

Several new, unorthogonalized, basis vectors are generated and are then orthogonalized with respect to the subspace already generated. Instead of generating a basis, such a method generates a series of low-dimensional orthogonal subspaces.

If conjugate gradient methods are considered to generate a factorization of a tridiagonal reduction of the original matrix, then look-ahead methods generate a block factorization of a block tridiagonal reduction of the matrix.

Keeping the block size constant throughout the iteration leads to the Block Lanczos algorithm and the Block Conjugate Gradient method (see O'Leary [159]). In fact, one can show that the spectrum of the matrix is effectively reduced by the smallest eigenvalues, where is the block size.