Dealing with linear dependence during the iterations of the restarted block Lanczos methods

Dedicated to Richard Varga on the occasion of his 70th birthday The Lanczos method can be generalized to block form to compute multiple eigenvalues without the need of any deflation techniques. The block Lanczos method reduces a general sparse symmetric matrix to a block tridiagonal matrix via a Gram-Schmidt process. During the iter-ations of the block Lanczos method an off-diagonal block of the block tridiagonal matrix may become singular, implying that the new set of Lanczos vectors are linearly dependent on the previously generated vec-tors. Unlike the single vector Lanczos method, this occurrence of linearly dependent vectors may not imply an invariant subspace has been com-puted. This difficulty of a singular off-diagonal block is easily overcome in non-restarted block Lanczos methods, see Golub and Underwood [12], and Ruhe [30]. The same schemes applied in non-restarted block Lanczos methods can also be applied in restarted block Lanczos methods. This al-lows the largest possible subspace to be built before restarting. However, in some cases a modification of the restart vectors is required or a singu-lar block will continue to reoccur. In this paper we examine the different schemes mentioned in [12, 30] for overcoming a singular block for the restarted block Lanczos methods, namely the restarted method reported in [12] and the Implicitly Restarted Block Lanczos (IRBL) method devel-oped by Baglama et al. [3]. Numerical examples are presented to illustrate the different strategies discussed. block Lanczos method, eigenvalues, implicit restarting, singular block, poly-nomial acceleration