Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



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
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 $ N \times N$ matrix the eigenvalues can be determined in $ O({\log ^2}N)$ time with $ {N^2}$ processors and $ O(N)$ time with N processors. The method is compared with a parallel variant of bisection that requires $ O({N^2})$ time on a single processor, $ O(N)$ time with N processors, and $ O(\log N)$ time with $ {N^2}$ processors.

References [Enhancements On Off] (What's this?)

Similar Articles

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

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

Additional Information

Keywords: Parallel computing, symmetric tridiagonal matrix, eigenvalues
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society