On computing the singular value decomposition

[摘要] The most well-known and widely-used algorithm for computing the Singular Value Decomposition (SVD) of an m x n rectangular matrix A nowadays is the Golub-Reinsch algorithm [1971]. In this paper, it is shown that by (1) first triangularizing the matrix A by Householder transformations before bidiagonalizing it, and (2) accumulating some left transformations on a n x n array instead of on an m x n array, the resulting algorithm is often more efficient than the Golub-Reinsch algorithm, especially for matrices with considerably more rows than columns (m >> n), such as in least squares applications. The two algorithms are compared in terms of operation counts, and computational experiments that have been carried out verify the theoretical comparisons. The modified algorithm is more efficient even when m is only slightly greater than n, and in some cases can achieve as much as 50% savings when m >> n. If accumulation of left transformations is desired, then $n^2$ extra storage locations are required (relatively small if m >> n), but otherwise no extra storage is required. The modified algorithm uses only orthogonal transformations and is therefore numerically stable. In the Appendix, we give the Fortran code of a hybrid method which automatically selects the more efficient of the two algorithms to use depending upon the input values for m and n.

[学科分类] 计算机科学（综合）