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

Author:
Axel Ruhe

Journal:
Math. Comp. **33** (1979), 680-687

MSC:
Primary 65F15

DOI:
https://doi.org/10.1090/S0025-5718-1979-0521282-9

MathSciNet review:
521282

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 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.

**[1]**D. BOLEY & G. H. GOLUB,*Inverse Eigenvalue Problems for Band Matrices*, Rep. STAN-CS-77-623, Stanford University, 1977. MR**0474741 (57:14375)****[2]**J. CULLUM,*The Simultaneous Computation of a Few Algebraically Largest and Smallest Eigenvalues of a Large, Sparse, Symmetric Matrix*, Rep. RC6827 IBM Research, Yorktown Heights, N. Y., 1977. MR**508328 (80d:65045)****[3]**J. CULLUM & W. E. DONATH,*A Block Generalization of the Symmetric s-Step Lanczos Algorithm*, Rep. RC4845, IBM Research, Yorktown Heights, N. Y., 1974.**[4]**J. W. DANIEL, W. B. GRAGG, L. KAUFMAN & G. W. STEWART, "Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization,"*Math. Comp.*, v. 30, 1976, pp. 772-795. MR**0431641 (55:4638)****[5]**G. H. GOLUB & R. UNDERWOOD, "The block Lanczos method for computing eigenvalues,"*Mathematical Software*III, (J. R. Rice, Ed.), Academic Press, New York, 1977, pp. 361-377. MR**0474742 (57:14376)****[6]**W. KAHAN & B. PARLETT,*An Analysis of Lanczos Algorithms for Symmetric Matrices*, Tech. Rep. ERL-M467, Univ. California, Berkeley, 1974.**[7]**C. LANCZOS, "An iteration method for the solution of the eigenvalue problem of linear differential and integral operators,"*J. Res. Nat. Bur. Standards*, v. 45, 1950, pp. 255-282. MR**0042791 (13:163d)****[8]**J. G. LEWIS,*Algorithms for Sparse Matrix Eigenvalue Problems*, Rep. STAN-CS-77-595, Stanford, 1977.**[9]**C. C. PAIGE, "Practical use of the symmetric Lanczos process with re-orthogonalization,"*BIT*, v. 10, 1970, pp. 183-195. MR**0264839 (41:9430)****[10]**C. C. PAIGE,*The Computation of Eigenvalues and Eigenvectors of Very Large Sparse Matrices*, Ph. D. Thesis, London University, 1971.**[11]**C. C. PAIGE, "Computational variants of the Lanczos method for the eigenproblem,"*J. Inst. Math. Appl.*, v. 10, 1972, pp. 373-381. MR**0334480 (48:12799)****[12]**B. PARLETT & D. S. SCOTT,*The Lanczos Algorithm with Implicit Deflation*, Rep. ERL M77/70, Univ. California, Berkeley, 1977.**[13]**A. RUHE, "Iterative eigenvalue algorithms for large symmetric matrices,"*ISNM*24,*Proc. Conf. Eigenwertprobleme Oberwolfach*1972, Birkhauser Verlag, Basel and Stuttgart, 1974, pp. 97-115. MR**0416000 (54:4077)****[14]**A. RUHE, "Computation of eigenvalues and eigenvectors,"*Sparse Matrix Techniques Copenhagen*1976, Lecture Notes in Math., vol. 572, Springer-Verlag, Berlin-Heidelberg-New York, 1977, pp. 130-184. MR**0440891 (55:13759)****[15]**A. RUHE & T. WIBERG, "The method of conjugate gradients used in inverse iteration,"*BIT*, v. 12, 1972, pp. 543-554. MR**0327013 (48:5355)****[16]**R. UNDERWOOD,*An Iterative Block Lanczos Method for the Solution of Large Sparse Symmetric Eigenproblems*, Rep. STAN-CS-75-496, Stanford University, 1975.**[17]**J. H. WILKINSON & C. REINSCH (Eds.),*Handbook for Automatic Computation*, Vol. II:*Linear Algebra*, Springer-Verlag, Berlin-Heidelberg-New York, 1971. MR**0461856 (57:1840)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65F15

Retrieve articles in all journals with MSC: 65F15

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1979-0521282-9

Article copyright:
© Copyright 1979
American Mathematical Society