A parallel algorithm for computing the eigenvalues of
a symmetric tridiagonal matrix
by P. N. Swarztrauber,
Mathematics of Computation,
20(1993), pp. 651-668.
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 NxN matrix the eigenvalues can
be determined in (log2N)2 time with
N2 processors and O(N)
time with N processors. The method is compared with a parallel
variant of bisection that requires O(N2) time on a single
processor, O(N) time with N processors and O(log N)
time with N2 processors.
Last updated July 14, 1998.
Mail comments to Paul Swarztrauber.