The spectral transformation Lánczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems

Ericsson, Thomas; Ruhe, Axel

doi:10.1090/S0025-5718-1980-0583502-2

The spectral transformation Lánczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems
HTML articles powered by AMS MathViewer

by Thomas Ericsson and Axel Ruhe PDF

Math. Comp. 35 (1980), 1251-1268 Request permission

Abstract:

A new algorithm is developed which computes a specified number of eigenvalues in any part of the spectrum of a generalized symmetric matrix eigenvalue problem. It uses a linear system routine (factorization and solution) as a tool for applying the Lanczos algorithm to a shifted and inverted problem. The algorithm determines a sequence of shifts and checks that all eigenvalues get computed in the intervals between them. It is shown that for each shift several eigenvectors will converge after very few steps of the Lanczos algorithm, and the most effective combination of shifts and Lanczos runs is determined for different sizes and sparsity properties of the matrices. For large problems the operation counts are about five times smaller than for traditional subspace iteration methods. Tests on a numerical example, arising from a finite element computation of a nuclear power piping system, are reported, and it is shown how the performance predicted bears out in a practical situation.

References

Hybrid Sturm Sequence and Simultaneous Iteration Methods

J. H. Argyris, Th. L. Johnsen, R. A. Rosanoff, and J. R. Roy, On numerical error in the finite element method, Comput. Methods Appl. Mech. Engrg. 7 (1976), no. 2, 261–282. MR 657963, DOI 10.1016/0045-7825(76)90017-7

Numerical Methods in Finite Element Analysis

James R. Bunch and Linda Kaufman, Some stable methods for calculating inertia and solving symmetric linear systems, Math. Comp. 31 (1977), no. 137, 163–179. MR 428694, DOI 10.1090/S0025-5718-1977-0428694-0
J. Alan George, Solution of linear systems of equations: direct methods for finite element problems, Sparse matrix techniques (Adv. Course, Technical Univ. Denmark, Copenhagen, 1976) Lecture Notes in Math., Vol. 572, Springer, Berlin, 1977, pp. 52–101. MR 0440883
Paul S. Jensen, The solution of large symmetric eigenproblems by sectioning, SIAM J. Numer. Anal. 9 (1972), 534–545. MR 315880, DOI 10.1137/0709049
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
C. C. Paige, Computational variants of the Lanczos method for the eigenproblem, J. Inst. Math. Appl. 10 (1972), 373–381. MR 334480, DOI 10.1093/imamat/10.3.373
Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. MR 570116
B. N. Parlett and D. S. Scott, The Lanczos algorithm with selective orthogonalization, Math. Comp. 33 (1979), no. 145, 217–238. MR 514820, DOI 10.1090/S0025-5718-1979-0514820-3
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

Matrix Eigensystem Routines EISPACK Guide

Gilbert Strang and George J. Fix, An analysis of the finite element method, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1973. MR 0443377

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