A Parallel Algorithm for Computing the Singular Value Decomposition of a Matrix

A parallel algorithm for computing the singular value decomposition of a matrix is presented. The algorithm uses a divide and conquer procedure based on a rank one modification of a bidiagonal matrix. Numerical difficulties associated with forming the product of a matrix with its transpose are avoided, and numerically stable formulae for obtaining the left singular vectors after computing updated right singular vectors are derived. A deflation technique is described that, together with a robust root finding method, assures computation of the singular values to full accuracy in the residual and also assures orthogonality of the singular vectors.