PARALLEL COMPUTATION OF THE SINGULAR VALUE DECOMPOSITION ON TREE ARCHITECTURES

B. B. ZHOU AND R. P. BRENT

Abstract

We describe three new Jacobi orderings for parallel computation of SVD problems on tree architectures. The first ordering uses the high bandwidth of a perfect binary fat-tree to minimise global interprocessor communication costs. The second is a new ring ordering which may be implemented efficiently on an ordinary binary tree. By combining these two orderings, an efficient new ordering, well suited for implementation on the Connection Machine CM5, is obtained.

Comments

Only the Abstract of [2] is given here. The full report appeared as [2], and a shorter version appeared as [3]. The idea of using an ordering adapted to the tree architecture was introduced by Lee, Luk and Boley in [1].

References

1. T. J. Lee, F. T. Luk and D. L. Boley, “Computing the SVD on a fat-tree architecture”, Proc. NATO Advanced Study Institute on Linear Algebra for Large Scale and Real-Time Applications, Leuven, Belgium, August 1992, 231–240.

2. B. B. Zhou and R. P. Brent, Parallel Computation of the Singular Value Decomposition on Tree Architectures, Technical Report TR-CS-93-05, Computer Sciences Laboratory, ANU, January 1993 (revised May 1993), 14 pp. rpb138tr.

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, Algorithms and Applications (S. Hariri and P. B. Berra, eds.), CRC Press, Ann Arbor, 1993, 128–131. rpb138.

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. Singular values, singular value decomposition, SVD, eigenvalues, Jacobi algo-

rithm, Jacobi ordering, tree architecture, fat tree.

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