Explicitly restarted Lanczos algorithms in an MPP environment

The Lanczos algorithm is one of the principal methods for the computation o f a small part of the eigenspectrum of large, sparse, real symmetric matric es. A single-vector, explicitly restarted variant of the Lanczos method is proposed in this paper. The algorithm finds only one eigenpair at a time us ing a deflation technique in which the Lanczos factorization for the curren t eigenpair is generated in the null space of all previously computed eigen vectors. This approach yields a fixed k-step restarting scheme which permit s short Lanczos factorizations and almost completely eliminates the reortho gonalization among the Lanczos vectors. The orthogonalization strategy deve loped falls naturally into the class of selective orthogonalization strateg ies as classified by Simon. 'Reverse communication' software for the implem entation of the proposed variant on a Connection Machine CM-200 with 8K pro cessors and on a Gray T3D with 32 processors is discussed. Test results on the CM-200 using examples from the Harvell-Boeing collection of sparse matr ices show the method to be very effective when compared with Sorensen's sta te-of-the-art routine taken from the ARPACK library. The method has fixed, small storage requirements, copes easily with genuinely multiple eigenvalue s and is guaranteed to converge to the desired eigenvalues. (C) 1999 Elsevi er Science B.V. All rights reserved.