BLOCK-JACOBI SVD ALGORITHMS FOR DISTRIBUTED MEMORY SYSTEMS II: MESHES∗
Martin Bečka, Marián Vajteršic · International Journal of Parallel Emergent and Distributed Systems · 1999
This paper deals with a parallelization of the two-sided Jacobi algorithm for computation of Singular Value Decomposition (SVD) on a computer with p processors, which are organized into a two-dimensional √p × √p mesh configuration. This work represents a continuation of our paper (Part I, to appear in J. Parallel Algorithms and Applications), which described a parallelization approach by columns and efficient ordering strategies for the hypercube and ring topologies. Our parallelization approach is based on slicing the matrices by rows and columns. The orderings developed for rings and hypercubes are adopted here and we show a proper assignment of submatrices to processors that enables their efficient parallel execution. A complexity comparison to the column-based algorithm is given. Parallel computational experiments on a Paragon system are presented and discussed for two test matrices.