An Improved Algorithm for Computing the Singular Value Decomposition
Tony Fan-Cheong Chan · ACM Transactions on Mathematical Software · 1982
The most well-known and widely used algorithm for computing the Singular Value Decomposition (SVD) A ---U ~V T of an m x n rectangular matrix A is the Golub-Reinsch algorithm (GR-SVD).In this paper, an improved version of the original GR-SVD algorithm is presented.The new algorithm works best for matrices with m >> n, but is more efficient even when m is only slightly greater than n (usually when m ~ 2n) and in some cases can achieve as much as 50 percent savings.If the matrix U ~s exphcltly desired, then n 2 extra storage locations are required, but otherwise no extra storage is needed.The two main modifications are: (1) first triangularizing A by Householder transformations before bldmgonahzing it (thin idea seems to be widely known among some researchers in the field, but as far as can be determined, neither a detailed analysis nor an lmplementatmn has been published before), and (2) accumulating the left Givens transformations in GR-SVD on an n x n array instead of on an m x n array.A PFORT-verified FORTRAN Implementation m included.Comparisons with the EISPACK SVD routine are given.