×

A parallel algorithm for computing the singular value decomposition of a matrix. (English) Zbl 0797.65037

The paper focuses on the computation of the singular value decomposition of a real matrix by divide and conquer mechanisms based on a rank one modification of a bidiagonal matrix. Algorithms founded on this technique have proved to be accurate and efficient for both serial and parallel computation of eigensystems of symmetric tridiagonal matrices.
Section 2 presents a review of the rank one updating techniques used for the symmetric tridiagonal eigenproblem. Section 3 continues with a discussion of some difficulties arising in the design of a singular value decomposition algorithm. Section 4 describes the basic divide and conquer step. 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. Section 5 and 6 are devoted to finite precision deflation rules.
The described deflation technique 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. Section 7 covers implementations of the divide and conquer algorithm and the results of numerical experiments.
The results suggest that, as for the symmetric tridiagonal eigenproblem, the divide and conquer method developed in sections 4-5 provides a fast and accurate serial alternative to the fastest serial method for solving the problems of very small order and the bisection and inverse iteration.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65Y05 Parallel numerical computation
PDFBibTeX XMLCite
Full Text: DOI