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

M. Gu, J. Demmel, Inderjit Dhillon

Abstract:   We present a new algorithm for computing the singular value decomposi- tion (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 al- gorithm (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 12n3 to 8 3 n3, 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(n2) storage. This makes the SVD a much more economical tool than it was before.

Download: pdf

Citation

  • Efficient Computation of the Singular Value Decomposition with Applications to Least Squares Problems (pdf)
    M. Gu, J. Demmel, I. Dhillon.
    Technical Report LBL-36201, October 1994.

    Bibtex: