LINEAR ALGEBRA RESEARCH ON THE AP1000

R. P. BRENT, A. CZEZOWSKI, M. HEGLAND, P. E. STRAZDINS, AND B. B. ZHOU

Abstract

This paper gives a report on various results of the Linear Algebra Project on the Fujitsu AP1000 in 1993. These include the general implementation of Distributed BLAS Level 3 subroutines (for the scattered storage scheme). The performance and user interface issues of the implementation are discussed. Implementations of Distributed BLAS-based LU Decomposition, Cholesky Factorization and Star Product algorithms are described.

The porting of the Basic Fourier Functions, written for the Fujitsu-ANU Area-4 Project, to the AP1000, is discussed. While the parallelization of the main FFT algorithm only involves communication on a single “transposition” step, several optimizations, including fast roots of unity calculation, are required for its efficient implementation.

Some optimizations of the Hestenes Singular Value Decomposition algorithm have been investigated, including a “BLAS Level 3”-like kernel for the main computation, and partitioning strategies. A study is made of how the optimizations affect convergence.

Finally, work on implementing QR Factorization on the AP1000 is discussed. The Householder QR method was found to be more efficient than the Givens QR method.

Comments

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

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 QRD algorithms on the Fujitsu AP1000”, Proc. 17th Australian Computer Science Conference, special issue of Australian Computer Science Communications 16 (1994), 733–743. rpb145

3. R. P. Brent, A. Czezowski, M. Hegland, P. E. Strazdins and B. B. Zhou, “Linear algebra research on the AP1000”, Proc. Second Parallel Computing Workshop, Fujitsu Laboratories, Kawasaki, Japan, November 1993, P1-L1–P1-L13. rpb146

1991 Mathematics Subject Classification. Primary 65H17; Secondary 65T20, 65Y05, 65Y10, 68Q22. Key words and phrases. BLAS, Basic Linear Algebra Subroutines, FFT, Fast Fourier Transform, Lin-

pack benchmark, MIMD, matrix star product, orthogonal factorisation, QR factorisation, Givens method, Householder method, singular value decomposition, Hestenes method, message-passing.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1993, the authors. rpb146a typeset using AMS-L^{A}TEX

(Brent, Zhou) Computer Sciences Laboratory, Australian National University, Canberra, ACT 0200

E-mail address, Brent, Zhou: {rpb,bing}@cslab.anu.edu.au

(Czezowski, Strazdins) Computer Science Department, Australian National University, Canberra, ACT 0200

E-mail address, Strazdins: peter@cs.anu.edu.au

(Hegland) School of Mathematical Sciences, Australian National University, Canberra, ACT 0200

E-mail address, Hegland: marcus@thrain.anu.edu.au