A divide-and-conquer algorithm for the bidiagonal SVD. (English) Zbl 0821.65019
A stable and efficient bidiagonal divide-and-conquer algorithm (BDC) for solving the problem of the singular value decomposition (SVD) is presented. The known divide-and-conquer algorithms suffer from a potential loss of orthogonality among the computed singular vectors unless extended precision arithmetic is used. The proposed BDC algorithm uses a partitioning of the original matrix and computes orthogonal matrices \((Q,q)\) and \(W\) such that
\[
B = (Qq) {M \choose 0} W^ T,
\]
where \(M\) is an \(N \times N\) matrix with nonzero elements only in the first column and the diagonal. Finally it finds the singular values of \(B\) by computing the SVD \(M = U \Omega V^ T\), where \(U\) and \(V\) are orthogonal matrices, and then computes the singular vector matrices of \(B\) as \((QU,q)\) and \(WV\), respectively. A generalization that computes the SVD of a lower banded matrix is also presented.
Reviewer: I.Dimov (Sofia)
MSC:
65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
65F20 | Numerical solutions to overdetermined systems, pseudoinverses |