BLOCK-JACOBI SVD ALGORITHMS FOR DISTRIBUTED MEMORY SYSTEMS I: HYPERCUBES AND RINGS*

* This work has been carried out within the framework of the research projects STABILE (INCO-COP96 0237) of the European Commission and Algorithmic Designs for Solving Some Problems of Parallel Numerics on Supercomputers of the Scientific Grant Agency of Slovak Republic and Slovak Academy of Sciences (VEGA).

Abstract

The paper presents parallel algorithms for efficient solution of the Singular Value Decomposition (SVD) problem by the block two-sided Jacobi method. In this part of the work, we show how the method may be used on MIMD computers with hypercube and ring topologies. We analyse three types of orderings for solving SVD on block-structured submatrices from the point of view of communication requirements and suitability for parallel execution of the computational process The algorithms map well onto the hypercube topology. Two of the ordering schemes can also be directly implemented on rings. Results obtained on an Intel Paragon are shown and discussed for all the three types of orderings.

Keywords:

• Parallel linear algebra
• SVD
• Hypercube
• Ring

Notes

* This work has been carried out within the framework of the research projects STABILE (INCO-COP96 0237) of the European Commission and Algorithmic Designs for Solving Some Problems of Parallel Numerics on Supercomputers of the Scientific Grant Agency of Slovak Republic and Slovak Academy of Sciences (VEGA).