Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Faster SVD for Matrices with Small $m/n$

Faster SVD for Matrices with Small $m/n$

File(s)
94-1414.pdf (704.95 KB)
94-1414.ps (278.77 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6196
Collections
Computer Science Technical Reports
Author
Bau, David
Abstract

The singular values of a matrix are conventionally computed using either the bidiagonalization algorithm by Golub and Reinsch (1970) when $m/n less than 5/3$, or the algorithm by Lawson and Hanson (1974) and Chan (1982) when $m/n greater than 5/3.$ However, there is an algorithm that is faster and that does not involve a discontinuous choice, as follows: in all cases, perform a QR factorization as in Lawson-Hanson-Chan, but rather than do this right at the beginning, do it after zeros have already been introduced in the first $j = 2n - m$ rows and columns. The same technique applies when computing singular vectors, with one small modification. If left singular vectors are needed, the new algorithm becomes advantageous only when $m greater than 1.2661n$, and the best $j$ in this case is $3n - m$. The benefits of the new algorithm appear in terms of classical scalar floating-point operation counts; the effects of locality and parallelization are not considered in the analysis.

Date Issued
1994-03
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR94-1414
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance