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.
- Topics:
- Numerical Linear Algebra
Download: pdf
Citation
- Efficient Computation of the Singular Value Decomposition with Applications to Least Squares Problems (pdf, software)
M. Gu, J. Demmel, I. Dhillon.
Technical Report LBL-36201, October 1994.
Bibtex: