Implementation aspects of band Lanczos algorithms for computation of eigenvalues of large sparse symmetric matrices

Ruhe, Axel

doi:10.1090/S0025-5718-1979-0521282-9

Implementation aspects of band Lanczos algorithms for computation of eigenvalues of large sparse symmetric matrices
HTML articles powered by AMS MathViewer

by Axel Ruhe PDF

Math. Comp. 33 (1979), 680-687 Request permission

Abstract:

A band Lanczos algorithm for the iterative computation of eigenvalues and eigenvectors of a large sparse symmetric matrix is described and tested on numerical examples. It starts with a p dimensional subspace, and computes an orthonormal basis for the Krylov spaces of A, generated from this starting subspace, in which A is represented by a $2p + 1$ band matrix, whose eigenvalues can be computed. Special emphasis is given to devising an implementation that gives a satisfactory numerical orthogonality, with a simple program and few arithmetic operations.

References

D. Boley and G. H. Golub, Inverse eigenvalue problems for band matrices, Numerical analysis (Proc. 7th Biennial Conf., Univ. Dundee, Dundee, 1977) Lecture Notes in Math., Vol. 630, Springer, Berlin, 1978, pp. 23–31. MR 0474741
Jane Cullum, The simultaneous computation of a few of the algebraically largest and smallest eigenvalues of a large, sparse, symmetric matrix, BIT 18 (1978), no. 3, 265–275. MR 508328, DOI 10.1007/BF01930896

A Block Generalization of the Symmetric s-Step Lanczos Algorithm

J. W. Daniel, W. B. Gragg, L. Kaufman, and G. W. Stewart, Reorthogonalization and stable algorithms for updating the Gram-Schmidt $QR$ factorization, Math. Comp. 30 (1976), no. 136, 772–795. MR 431641, DOI 10.1090/S0025-5718-1976-0431641-8
G. H. Golub and R. Underwood, The block Lanczos method for computing eigenvalues, Mathematical software, III (Proc. Sympos., Math. Res. Center, Univ. Wisconsin, Madison, Wis., 1977) Publ. Math. Res. Center, No. 39, Academic Press, New York, 1977, pp. 361–377. MR 0474742

An Analysis of Lanczos Algorithms for Symmetric Matrices

Cornelius Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Research Nat. Bur. Standards 45 (1950), 255–282. MR 0042791

Algorithms for Sparse Matrix Eigenvalue Problems

C. C. Paige, Practical use of the symmetric Lanczos process with re-orthogonalization, Nordisk Tidskr. Informationsbehandling (BIT) 10 (1970), 183–195. MR 264839, DOI 10.1007/bf01936866

The Computation of Eigenvalues and Eigenvectors of Very Large Sparse Matrices

C. C. Paige, Computational variants of the Lanczos method for the eigenproblem, J. Inst. Math. Appl. 10 (1972), 373–381. MR 334480

The Lanczos Algorithm with Implicit Deflation

A. Ruhe, Iterative eigenvalue algorithms for large symmetric matrices, Numerische Behandlung von Eigenwertaufgaben (Tagung, Oberwolfach, 1972), Internat. Schr. Numer. Math., Band 24, Birkhäuser, Basel, 1974, pp. 97–115. MR 0416000
Axel Ruhe, Computation of eigenvalues and eigenvectors, Sparse matrix techniques (Adv. Course, Technical Univ. Denmark, Copenhagen, 1976) Lecture Notes in Math., Vol. 572, Springer, Berlin, 1977, pp. 130–184. MR 0440891
Axel Ruhe and Torbjörn Wiberg, The method of conjugate gradients used in inverse iteration, Nordisk Tidskr. Informationsbehandling (BIT) 12 (1972), 543–554. MR 327013, DOI 10.1007/bf01932964

An Iterative Block Lanczos Method for the Solution of Large Sparse Symmetric Eigenproblems

Handbook for automatic computation. Vol. II, Die Grundlehren der mathematischen Wissenschaften, Band 186, Springer-Verlag, New York-Heidelberg, 1971. Linear algebra; Compiled by J. H. Wilkinson and C. Reinsch. MR 0461856