Techreport,

Efficient Computation of the Singular Value Decomposition with Applications to Least Squares Problems

, , and .
(1994)

Abstract

We present a new algorithm for computing the singular value decomposition (SVD) of a matrix. The algorithm is based on using divide-and-conquer to compute the SVD of a bidiagonal matrix. Compared to the previous algorithm (based on QR-iteration) the new algorithm is at least 9 times faster on bidiagonal matrices of dimension n = 400, when running on a DEC Alpha with optimized BLAS. The speedup increases with dimension n. For the dense singular value decomposition, the speedup ranges from 2.2 to 3.9 for n = 400. When used to solve dense, square linear least squares problems, the operation count drops from 12n 3 to 8 3 n 3 , and the speedup ranges from 2.3 to 3.8 for n = 400. This means using the SVD for the least squares problem averages only 4.8 times slower than using simple QR decomposition, whereas it used to be over 15 times slower. We show how to modify the old least squares solver based on the SVD with QR-iteration to attain slightly better speedup, at the cost of O(n 2 ...

Tags

Users

  • @folke

Comments and Reviews