Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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 $ 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 [Enhancements On Off] (What's this?)

  • [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)

Similar Articles

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

American Mathematical Society