A high performance parallelization scheme for the Hessenberg double shift QR algorithm
✍ Scribed by Reiji Suda; Akira Nishida; Yoshio Oyanagi
- Book ID
- 104304740
- Publisher
- Elsevier Science
- Year
- 1999
- Tongue
- English
- Weight
- 924 KB
- Volume
- 25
- Category
- Article
- ISSN
- 0167-8191
No coin nor oath required. For personal study only.
✦ Synopsis
We propose a new parallelization scheme for the Hessenberg double shift QR algorithm. Our scheme allows software pipelining and communication latency hiding, and gives almost perfect load balance. An asymptotic parallelizing overhead analysis shows that our scheme attains the best possible scalability of the double shift QR algorithm, and that the overheads are less than the multishift algorithm when n xp 2 , where n is the matrix size and p is the number of processors. Its high exploitation of the parallelism of the double shift QR algorithm is demonstrated by an implementation on Fujitsu AP1000+ multicomputer system.