A parallel algorithm for computing the eigenvalues of a symmetric tridiagonal matrix

Author:
Paul N. Swarztrauber

Journal:
Math. Comp. **60** (1993), 651-668

MSC:
Primary 65F15; Secondary 65Y05

DOI:
https://doi.org/10.1090/S0025-5718-1993-1164126-4

MathSciNet review:
1164126

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A parallel algorithm, called polysection, is presented for computing the eigenvalues of a symmetric tridiagonal matrix. The method is based on a quadratic recurrence in which the characteristic polynomial is constructed on a binary tree from polynomials whose degree doubles at each level. Intervals that contain exactly one zero are determined by the zeros of polynomials at the previous level which ensures that different processors compute different zeros. The signs of the polynomials at the interval endpoints are determined a priori and used to guarantee that all zeros are found. The use of finite-precision arithmetic may result in multiple zeros; however, in this case, the intervals coalesce and their number determines exactly the multiplicity of the zero. For an matrix the eigenvalues can be determined in time with processors and time with *N* processors. The method is compared with a parallel variant of bisection that requires time on a single processor, time with *N* processors, and time with processors.

**[1]**W. Barth, R. S. Martin, and J. H. Wilkinson,*Handbook Series Linear Algebra: Calculation of the eigenvalues of a symmetric tridiagonal matrix by the method of bisection*, Numer. Math.**9**(1967), no. 5, 386–393. MR**1553954**, https://doi.org/10.1007/BF02162154**[2]**James R. Bunch, Christopher P. Nielsen, and Danny C. Sorensen,*Rank-one modification of the symmetric eigenproblem*, Numer. Math.**31**(1978/79), no. 1, 31–48. MR**508586**, https://doi.org/10.1007/BF01396012**[3]**J. J. M. Cuppen,*A divide and conquer method for the symmetric tridiagonal eigenproblem*, Numer. Math.**36**(1980/81), no. 2, 177–195. MR**611491**, https://doi.org/10.1007/BF01396757**[4]**James Demmel and W. Kahan,*Accurate singular values of bidiagonal matrices*, SIAM J. Sci. Statist. Comput.**11**(1990), no. 5, 873–912. MR**1057146**, https://doi.org/10.1137/0911052**[5]**J. Demmel and W. Gragg,*On computing accurate singular values and eigenvalues of acyclic matrices*, IMA Preprint Series, no. 962, Institute for Math. and its Appl., Univ. of Minnesota, 1992.**[6]**J. J. Dongarra and D. C. Sorensen,*A fully parallel algorithm for the symmetric eigenvalue problem*, SIAM J. Sci. Statist. Comput.**8**(1987), no. 2, S139–S154. Parallel processing for scientific computing (Norfolk, Va., 1985). MR**879400**, https://doi.org/10.1137/0908018**[7]**D. J. Evans, J. Shanehchi, and C. C. Rick,*A modified bisection algorithm for the determination of the eigenvalues of a symmetric tridiagonal matrix*, Numer. Math.**38**(1981/82), no. 3, 417–419. MR**654106**, https://doi.org/10.1007/BF01396441**[8]**Ilse C. F. Ipsen and Elizabeth R. Jessup,*Solving the symmetric tridiagonal eigenvalue problem on the hypercube*, SIAM J. Sci. Statist. Comput.**11**(1990), no. 2, 203–229. MR**1037511**, https://doi.org/10.1137/0911013**[9]**W. Kahan,*Accurate eigenvalues of a symmetric tri-diagonal matrix*, Tech. Report CS41, Comput. Sci. Dept., Stanford University, July 22, 1966, with revisions to June 1968, available from the author at the University of California at Berkeley.**[10]**A. S. Krishnakumar and Martin Morf,*Eigenvalues of a symmetric tridiagonal matrix: a divide-and-conquer approach*, Numer. Math.**48**(1986), no. 3, 349–368. MR**826474**, https://doi.org/10.1007/BF01389480**[11]**Richard E. Ladner and Michael J. Fischer,*Parallel prefix computation*, J. Assoc. Comput. Mach.**27**(1980), no. 4, 831–838. MR**594702**, https://doi.org/10.1145/322217.322232**[12]**Sy-Shin Lo, Bernard Philippe, and Ahmed Sameh,*A multiprocessor algorithm for the symmetric tridiagonal eigenvalue problem*, SIAM J. Sci. Statist. Comput.**8**(1987), no. 2, S155–S165. Parallel processing for scientific computing (Norfolk, Va., 1985). MR**879401**, https://doi.org/10.1137/0908019**[13]**Ahmed H. Sameh and David J. Kuck,*A parallel QR algorithm for symmetric tridiagonal matrices*, IEEE Trans. Computers**C-26**(1977), no. 2, 147–153. MR**0449003****[14]**Robert Schreiber,*Computing generalized inverses and eigenvalues of symmetric matrices using systolic arrays*, Computing methods in applied sciences and engineering, VI (Versailles, 1983) North-Holland, Amsterdam, 1984, pp. 285–295. MR**806785****[15]**B. T. Smith, J. M. Boyle, J. J. Dongarra, B. S. Garbow, Y. Ikebe, V. C. Klema, and C. B. Moler,*Matrix eigensystem routines—EISPACK guide*, 2nd ed., Springer-Verlag, Berlin-New York, 1976. Lecture Notes in Computer Science, Vol. 6. MR**0494879****[16]**D. C. Sorensen and Ping Tak Peter Tang,*On the orthogonality of eigenvectors computed by divide-and-conquer techniques*, SIAM J. Numer. Anal.**28**(1991), no. 6, 1752–1775. MR**1135764**, https://doi.org/10.1137/0728087**[17]**Harold S. Stone,*Parallel tridiagonal equation solvers*, ACM Trans. Math. Software**1**(1975), no. 4, 289–307. MR**0388842**, https://doi.org/10.1145/355656.355657**[19]**Paul N. Swarztrauber,*A parallel algorithm for solving general tridiagonal equations*, Math. Comp.**33**(1979), no. 145, 185–199. MR**514818**, https://doi.org/10.1090/S0025-5718-1979-0514818-5**[20]**J. H. Wilkinson,*Handbook Series Linear Algebra. Calculation of the eigenvalues of a symmetric tridiagonal matrix by the method of bisection*, Numer. Math.**4**(1962), 362–367. MR**0148208**, https://doi.org/10.1007/BF01386333**[21]**J. H. Wilkinson,*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965. MR**0184422**

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

Retrieve articles in all journals with MSC: 65F15, 65Y05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1993-1164126-4

Keywords:
Parallel computing,
symmetric tridiagonal matrix,
eigenvalues

Article copyright:
© Copyright 1993
American Mathematical Society