Algorithm 581: An Improved Algorithm for Computing the Singular Value Decomposition [F1]
Tony Fan-Cheong Chan · ACM Transactions on Mathematical Software · 1982
The set of FORTRAN subroutines given here is an implementation of the algorithm [1] for computing the Singular Value Decomposition (SVD) of a general m by n rectangular matrix A defined as A = UWV T, where U is an m × min(m,n) matrix containing the left singular vectors, W is a diagonal matrix of size min(m, n) containing the singular values, and V is an n x min(m, n) matrix containing the right singular vectors.Note that m is allowed to be greater than or less than n.For ease of presentation, we assume m to be greater than or equal to n in the following discussion.The algorithm is an improvement of the Golub-Reinsch algorithm [4], which is implemented in subroutines SVD and MINFIT in EISPACK [3] and in subroutine SSVDC in LINPACK [2].It should be more efficient than the Golub-Reinsch algorithm when m is approximately larger tJ lan 2n, as is the case in many least squares applications.The algorithm has a hybrid nature.When m is aboat equal to n, the Golub-Reinsch algorithm is employed.When the ratio m/n is larger than a threshold value, which is determined by detailed operation counts [1], the improved algorithm is used.The improved algorithm first computes the QR factorization of A using Householder transformations, and then uses the Golub-Reinsch algorithm on R. A further improvement over the Golub-Reinsch algorithm is when the left singular