Solving the Symmetric Tridiagonal Eigenvalue Problem on the Hypercube
Author | : YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE. |
Publisher | : |
Total Pages | : 45 |
Release | : 1987 |
ISBN-10 | : OCLC:123340469 |
ISBN-13 | : |
Rating | : 4/5 (69 Downloads) |
Book excerpt: This paper describes implementations of Cuppen's 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 Intel's iPSC are presented. Cuppen's method is the most accurate of the three. Near maximal speedups are demonstrated for Cuppen's 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.