Solving the Symmetric Tridiagonal Eigenvalue Problem on the Hypercube.
YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
This paper describes implementations of Cuppens method, bisection, and multisection for the computation of all eigenvalues and eigenvectors of a symmetric tridiagonal matrix on a distributed-memory hypercube multiprocessor. Numerical results and timings for Intels iPSC are presented. Cuppens method is the most accurate of the three. Near maximal speedups are demonstrated for Cuppens method when little deflation occurs at intermediate steps, but speedups are significantly reduced when deflation leads to processor load imbalance. Bisection with inverse iteration is seen experimentally to be the fastest method sequentially and in parallel. The independent tasks comprising this approach lead to high parallel efficiency. The relative expected performance of parallel multisection is shown analytically to be problem dependent with arithmetic inefficiency arising in a wide class of problems. Moderate speedups are observed experimentally.
- Computer Hardware