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

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 and G. H. Golub, Inverse eigenvalue problems for band matrices, Numerical analysis (Proc. 7th Biennial Conf., Univ. Dundee, Dundee, 1977), Springer, Berlin, 1978, pp. 23–31. Lecture Notes in Math., Vol. 630. MR 0474741
  • [2] 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, https://doi.org/10.1007/BF01930896
  • [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, and G. W. Stewart, Reorthogonalization and stable algorithms for updating the Gram-Schmidt 𝑄𝑅 factorization, Math. Comp. 30 (1976), no. 136, 772–795. MR 0431641, https://doi.org/10.1090/S0025-5718-1976-0431641-8
  • [5] 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) Academic Press, New York, 1977, pp. 361–377. Publ. Math. Res. Center, No. 39. MR 0474742
  • [6] W. KAHAN & B. PARLETT, An Analysis of Lanczos Algorithms for Symmetric Matrices, Tech. Rep. ERL-M467, Univ. California, Berkeley, 1974.
  • [7] 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
  • [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, Nordisk Tidskr. Informationsbehandling (BIT) 10 (1970), 183–195. MR 0264839
  • [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. 10 (1972), 373–381. MR 0334480
  • [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, Numerische Behandlung von Eigenwertaufgaben (Tagung, Oberwolfach, 1972), Birkhäuser, Basel, 1974, pp. 97–115. Internat. Schr. Numer. Math., Band 24. MR 0416000
  • [14] Axel Ruhe, Computation of eigenvalues and eigenvectors, Sparse matrix techniques (Adv. Course, Technical Univ. Denmark, Copenhagen, 1976) Springer, Berlin, 1977, pp. 130–184. Lecture Notes in Math., Vol. 572. MR 0440891
  • [15] Axel Ruhe and Torbjörn Wiberg, The method of conjugate gradients used in inverse iteration, Nordisk Tidskr. Informationsbehandling (BIT) 12 (1972), 543–554. MR 0327013
  • [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] Handbook for automatic computation. Vol. II, Springer-Verlag, New York-Heidelberg, 1971. Linear algebra; Compiled by J. H. Wilkinson and C. Reinsch; Die Grundlehren der Mathematischen Wissenschaften, Band 186. MR 0461856

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