PARALLEL IMPLEMENTATION OF QRD ALGORITHMS ON THE FUJITSU AP1000

B. B. ZHOU AND R. P. BRENT

Abstract

This paper addresses several important aspects of parallel implementation of QR decomposition of a matrix on a distributed memory MIMD machine, the Fujitsu AP1000. They include: Among various QR decomposition algorithms, which one is most suitable for implementation on the AP1000? With the total number of cells given, what is the best aspect ratio of the array to achieve optimal performance? How efficient is the AP1000 in computing the QR decomposition of a matrix? To help answer these questions we have implemented various orthogonal factorisation algorithms on a 128-cell AP1000 located at the Australian National University. After extensive experiments some interesting results have been obtained and are presented in the paper.

Comments

Only the Abstract of [4] is given here. For related work see [1, 2, 3].

References

1. R. P. Brent and P. E. Strazdins, “Implementation of the BLAS level 3 and Linpack benchmark on the AP 1000”, Fujitsu Scientific and Technical Journal 29, 1 (March 1993), 61–70. rpb136

2. B. B. Zhou and R. P. Brent, “Parallel implementation of eigenvalue algorithms on distributed memory machines”, Proc. 16th Australian Computer Science Conference (edited by G. Gupta, G. Mohay and R. Topor), Brisbane, 3-5 Feb. 1993, 19–25. rpb137

3. B. B. Zhou and R. P. Brent, “Parallel computation of the singular value decomposition on tree architectures”, Proc. 22nd International Conference on Parallel Processing (St. Charles, Illinois, August 1993), Vol. 3, CRC Press, Ann Arbor, 1993, 128–131. rpb138.

4. B. B. Zhou and R. P. Brent, “Parallel implementation of QRD algorithms on the Fujitsu AP1000”, Proc. 17th Australian Computer Science Conference, Christchurch, New Zealand, Jan. 1994, to appear. Appeared as Tech. Report TR-CS-93-12, CSL, ANU, November 1993 11 pp. rpb145

Computer Sciences Laboratory, Australian National University, Canberra, ACT 0200 E-mail address: {bing,rpb}@cslab.anu.edu.au

1991 Mathematics Subject Classification. Primary 65H17; Secondary 65Y05, 65Y10, 68Q22. Key words and phrases. Orthogonal factorisation, QR factorisation, QR decomposition, Givens

method, Householder method, block Householder method, MIMD, message-passing, torus, grid. Copyright \begin{matrix}c \\ ◯ \end{matrix} 1993, the authors. rpb145a typeset using AMS-L^{A}TEX