A Parallel Algorithm for the Singular Value Problem in Bidiagonal Matrices.
Christian I. Trefftz, Philip K. McKinley, Tien-Yien Li, Zhonggang Zeng · 1995
This paper describes a parallel algorithm for finding the singular values of a bidiagonal matrix B. The algorithm finds the largest singular values by finding the corresponding eigenvalues of the symmetric tridiagonal (ST) matrix B T B and taking the square roots of those eigenvalues. The smallest singular values are calculated by computing the corresponding eigenvalues of another ST matrix T , which contains zeroes in the main diagonal and entries of B in the off-diagonals. Details of two implementations of the algorithm are described. One implementation uses the splitmerge algorithm to find the eigenvalues of ST matrices, and the other uses a bisection- based eigenvalue method. Performance results on an nCUBE-2 and a workstation cluster are presented. 1 Introduction The problem of finding the singular value decomposition (SVD) of an m \\Theta n real matrix A, with m n, can be stated as follows: Find the values oe 1 ; : : : ; oe n such that U T AV = diag(oe 1 ; : : : ;...