Efficient computation of the singular value decomposition on cube connected SIMD machine

The singular value decomposition (SVD) has many real-time applications. Recently, there has been much interest in developing efficient methods to compute SVD in parallel machines. This paper presents an efficient method for computing SVD in a cube connected SIMD (single instruction stream - multiple data stream) parallel computer. The method is based on a one-sided orthogonalization algorithm due to Hestenes. In a cube connected SIMD with n/2 processors, the SVD of an m by n matrix requires a computation time of (mn) per sweep. Although the time complexity (excluding communication time) is the same as that of the best known SVD method on linearly connected SIMD, the communication time is much smaller because the amount of data moved among the nodes is only about one half. The SVD of large matrices on a fixed size system is also discussed.