Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Computing the Generalized Singular Value Decomposition

Zhaojun Bai and James W. Demmel

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-92-720
December 1992

http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-720.pdf

We present a variation of Paige's algorithm for computing the generalized singular value decomposition (GSVD) of two matrices A and B. There are two innovations. The first is a new preprocessing step which reduces A and B to upper triangular forms satisfying certain rank conditions. The second is a new 2 by 2 triangular GSVD algorithm, which constitutes the inner loop of Paige's algorithm. We present proofs of stability and high accuracy of the 2 by 2 GSVD algorithm, and demonstrate it using examples on which all previous algorithms fail.

Keywords: generalized singular value decomposition, CS decomposition, matrix decomposition, Jacobi algorithm, Kogbetliantz algorithm


BibTeX citation:

@techreport{Bai:CSD-92-720,
    Author = {Bai, Zhaojun and Demmel, James W.},
    Title = {Computing the Generalized Singular Value Decomposition},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1992},
    Month = {Dec},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/6016.html},
    Number = {UCB/CSD-92-720},
    Abstract = {We present a variation of Paige's algorithm for computing the generalized singular value decomposition (GSVD) of two matrices <i>A</i> and <i>B</i>. There are two innovations. The first is a new preprocessing step which reduces <i>A</i> and <i>B</i> to upper triangular forms satisfying certain rank conditions. The second is a new 2 by 2 triangular GSVD algorithm, which constitutes the inner loop of Paige's algorithm. We present proofs of stability and high accuracy of the 2 by 2 GSVD algorithm, and demonstrate it using examples on which all previous algorithms fail.  <p>Keywords: generalized singular value decomposition, CS decomposition, matrix decomposition, Jacobi algorithm, Kogbetliantz algorithm}
}

EndNote citation:

%0 Report
%A Bai, Zhaojun
%A Demmel, James W.
%T Computing the Generalized Singular Value Decomposition
%I EECS Department, University of California, Berkeley
%D 1992
%@ UCB/CSD-92-720
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/6016.html
%F Bai:CSD-92-720