Parallel computation of the SVD on tree architectures

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

Abstract: dvi (3K), pdf (29K), ps (27K).

Paper: dvi (16K), pdf (71K), ps (52K).


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.


The idea of using an ordering adapted to the tree architecture was introduced by Lee, Luk and Boley [Proc. NATO ASI, Leuven, Belgium, August 1992, 231-240].

Go to next publication

Return to Richard Brent's index page