LAPACK Working Note 166: Computing the Bidiagonal SVD Using Multiple Relatively Robust Representations

Paul R. Willems, Bruno Lang and Christof Voemel

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-05-1376
2005

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/CSD-05-1376.pdf

We describe the design and implementation of a new algorithm for computing the singular value decomposition of a real bidiagonal matrix. This algorithm uses ideas developed by Grosser and Lang that extend Parlett's and Dhillon's MRRR algorithm for the tridiagonal symmetric eigenproblem. One key feature of our new implementation is, that k singular triplets can be computed using only O( nk) storage units and floating point operations, where n is the dimension of the matrix. The algorithm will be made available as routine xBDSCR in the upcoming new release of the LAPACK library.

BibTeX citation:

@techreport{Willems:CSD-05-1376,
    Author = {Willems, Paul R. and Lang, Bruno and Voemel, Christof},
    Title = {LAPACK Working Note 166: Computing the Bidiagonal SVD Using Multiple Relatively Robust Representations},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2005},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5648.html},
    Number = {UCB/CSD-05-1376},
    Abstract = {We describe the design and implementation of a new algorithm for computing the singular value decomposition of a real bidiagonal matrix. This algorithm uses ideas developed by Grosser and Lang that extend Parlett's and Dhillon's MRRR algorithm for the tridiagonal symmetric eigenproblem. One key feature of our new implementation is, that <i>k</i> singular triplets can be computed using only <i>O</i>(<i>nk</i>) storage units and floating point operations, where <i>n</i> is the dimension of the matrix. The algorithm will be made available as routine xBDSCR in the upcoming new release of the LAPACK library.}
}

EndNote citation:

%0 Report
%A Willems, Paul R.
%A Lang, Bruno
%A Voemel, Christof
%T LAPACK Working Note 166: Computing the Bidiagonal SVD Using Multiple Relatively Robust Representations
%I EECS Department, University of California, Berkeley
%D 2005
%@ UCB/CSD-05-1376
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5648.html
%F Willems:CSD-05-1376