Abstract
In this paper we present an algorithm, parallel in nature, for finding eigenvalues of a symmetric definite tridiagonal matrix pencil. Our algorithm employs the determinant evaluation, split-and-merge strategy and Laguerre's iteration. Numerical results on both single and multiprocessor computers are presented which show that our algorithm is reliable, efficient and accurate. It also enjoys flexibility in evaluating a partial spectrum.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
E. Anderson et al.,LAPACK User's Guide (SIAM, Philadelphia, 1992).
A.E. Berger, J.M. Solomon and M. Ciment, Higher order accurate tridiagonal difference methods for diffusion convection equations, in:Advances in Computer Methods for Partial Differential Equations III, eds. R. Vichnevetsky and R.S. Stepleman (IMACS, 1978) pp. 322–330.
C.F. Borges and W.B. Gragg, A parallel divide and conquer algorithm for the generalized real symmetric definite tridiagonal eigenproblem, preprint, Naval Post-Graduate School (1992).
R.F. Boisvert, Families of higher order accurate discretizations of some elliptic problems, SIAM J. Sci. Stat. Comp. 2 (1981) 268–284.
L. Collatz,Numerical Treatment of Differential Equations (Springer, Berlin, 1960).
J.J.M. Cuppen, A divide-and-conquer method for the symmetric tridiagonal eigenproblem, Numer. Math. 36 (1981) 177–195.
J.J. Dongarra and D.C. Sorensen, A fully parallel algorithm for the symmetric eigenvalue problem. SIAM J. Sci. Stat. Comp. 8 (1987) 139–154.
G.H. Golub and Van Loan,Matrix Computations (The Johns Hopkins University Press, Baltimore, MD, 1989).
B. Grieves and D. Dunn Symmetric matrix methods for Schrödinger eigenvectors, J. Phys. A: Math. Gen. 23 (1990) 5479–5491.
W. Kahan, Notes on Laguerre's iteration, unpublished research notes (1992).
L. Kaufman, An algorithm for the banded symmetric generalized matrix eigenvalue problem, SIAM J. Matrix Anal. Appl. 14 (1993) 372–389
K. Li and T.Y. Li, An algorithm for symmetric tridiagonal eigenproblems — divide and conquer with homotopy continuation, SIAM J. Sci. Comp. 14 (1993) 735–751.
K. Li and T. Y. Li, A homotopy algorithm for a symmetric generalized eigenproblem, Numer. Algor. 4 (1993) 167–195.
T.Y. Li and Z. Zeng, Laguerre's iteration in solving the symmetric tridiagonal eigenproblem — revisited, SIAM J. Sci. Comp., to appear.
S-S. Lo, B. Phillipe and A. Sameh, A multiprocessor algorithm for the symmetric tridiagonal eigenvalue problems, SIAM J. Sci. Stat. Comp. 8 (1987) 155–165.
R.D. Pantazis and D.B. Szyld, A multiprocessor method for the solution of the generalized eigenvalue problem on an interval,Parallel Processing for Scientific Computing, Proc. 4th SIAM Conf., eds. J. Dongarra, P. Messina, D.G. Sorensen and R.G. Voigt (SIAM, Philadelphia, PA, 1990) pp. 36–41.
B.N. Parlett,The Symmetric Eigenvalue Problem (Prentice-Hall, Englenwood Cliffs, NJ, 1980).
B. Philippe and B. Vital, Parallel implementations for solving generalized eigenvalue problems with symmetric sparse matrices. App. Numer. Math. 12 (1993) 391–402.
Y.M. Ram and G.M.L. Gladwell, Constructing a finite-element model of a vibratory rod from eigendata, J. Sound Vibration 165 (1993).
C.J. Ribbens and C. Beattie, Parallel solution of generalized symmetric tridiagonal eigenvalue problem on shared memory multiprocessors, Technical Report TR 92-47, Department of Computer Science, Virginia Polytechnic Institute and State University (1992).
B.T. Smith et al.,Matrix Eigensystem Routines — EISPACK Guide, 2nd ed. (Springer, New York, 1976).
G. Strang and G. Fix,An Analysis of the Finite Element Method (Prentice-Hall, Englewood Cliffs, NJ, 1973).
C. Trefftz, P. McKinley, T.Y. Li and Z. Zeng, A scalable eigenvalue solver for symmetric tridiagonal matrices,Proc. 6th SIAm Conf. on Parallel Processing for Scientific Computing (SIAM, 1993) pp. 602–609.
W. Weaver, Jr. and P.R. Johnson,Finite Elements for Structural Analysis (Prentice-Hall, NJ, 1984).
J.H. Wilkinson,The Algebraic Eigenvalue Problem (Oxford University Press, Oxford, 1965).
Author information
Authors and Affiliations
Additional information
Communicated by C. Brezinski
This research was supported in part by the Research Grant from University of West Florida.
This research was supported in part by NSF under Grant CCR-9024840.
Rights and permissions
About this article
Cite this article
Li, K., Li, TY. & Zeng, Z. An algorithm for the generalized symmetric tridiagonal eigenvalue problem. Numer Algor 8, 269–291 (1994). https://doi.org/10.1007/BF02142694
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02142694