On The Implementation Of A Fully Parallel Algorithm For The Symmetric Eigenvalue Problem

J. J. Dongarra; D. C. Sorensen

doi:10.1117/12.936874

4 April 1986 On The Implementation Of A Fully Parallel Algorithm For The Symmetric Eigenvalue Problem

J. J. Dongarra, D. C. Sorensen

Proceedings Volume 0696, Advanced Algorithms and Architectures for Signal Processing I; (1986) https://doi.org/10.1117/12.936874
Event: 30th Annual Technical Symposium, 1986, San Diego, United States

Abstract

In this paper we present a parallel algorithm for the symmetric algebraic eigenvalue problem. The algorithm is based upon a divide and conquer scheme suggested by Cuppen for computing the eigensystem of a symmetric tridiagonal matrix. We extend this idea to obtain a parallel algorithm that retains a number of active parallel processes that is greater than or equal to the initial number throughout the course of the computation. Computation of the eigensystem of the tridiagonal matrix is reviewed. Also, brief analysis of the numerical properties and sensitivity to round off error is presented to indicate where numerical difficulties may occur. We show how to explicitly overlap the initial reduction to tridiagonal form with the parallel computation of the eigensystem of the tridiagonal matrix. The algorithm is therefore able to exploit parallelism at all levels of the computation and is well suited to a variety of architectures. Computational results have been presented in [4] for several machines. These results are very encouraging with respect to both accuracy and speedup. A surprising result is that the parallel algorithm for the tridiagonal case, even when run in serial mode, can be significantly faster than the previously best sequential algorithm on large problems, and is effective on moderate size problems when run in serial mode.

Citation Download Citation

J. J. Dongarra and D. C. Sorensen "On The Implementation Of A Fully Parallel Algorithm For The Symmetric Eigenvalue Problem", Proc. SPIE 0696, Advanced Algorithms and Architectures for Signal Processing I, (4 April 1986); https://doi.org/10.1117/12.936874

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available