BLOCK-JACOBI SVD ALGORITHMS FOR DISTRIBUTED MEMORY SYSTEMS I: HYPERCUBES AND RINGS*
- 1 January 1999
- journal article
- research article
- Published by Taylor & Francis in Parallel Algorithms and Applications
- Vol. 13 (3) , 265-287
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
This publication has 8 references indexed in Scilit:
- A Parallel Ring Ordering Algorithm for Efficient One-Sided Jacobi SVD ComputationsJournal of Parallel and Distributed Computing, 1997
- On Parallel Jacobi OrderingsSIAM Journal on Scientific and Statistical Computing, 1989
- Triangular processor array for computing singular valuesLinear Algebra and its Applications, 1986
- Efficient implementation of Jacobi's diagonalization method on the DAPNumerische Mathematik, 1985
- The Solution of Singular-Value and Symmetric Eigenvalue Problems on Multiprocessor ArraysSIAM Journal on Scientific and Statistical Computing, 1985
- An Improved Algorithm for Computing the Singular Value DecompositionACM Transactions on Mathematical Software, 1982
- On Jacobi and Jacobi-like algorithms for a parallel computerMathematics of Computation, 1971
- Singular value decomposition and least squares solutionsNumerische Mathematik, 1970