next up previous contents index
Next: Computational Routines Up: Generalized Eigenvalue and Singular Previous: Generalized Nonsymmetric Eigenproblems (GNEP)   Contents   Index


Generalized Singular Value Decomposition (GSVD)

The generalized (or quotient) singular value decomposition of an m-by-n matrix A and a p-by-n matrix B is given by the pair of factorizations

\begin{displaymath}
A = U \Sigma_1 [0,\; R ] Q^T
\;\;\; {\rm and} \;\;\;
B = V \Sigma_2 [0, \; R ] Q^T \;.
\end{displaymath}

The matrices in these factorizations have the following properties:

$\Sigma_1$ and $\Sigma_2$ have the following detailed structures, depending on whether $m-r \geq 0$ or m-r < 0. In the first case, $m-r \geq 0$ , then

\begin{displaymath}
\Sigma_1 = \bordermatrix{ & k & l \cr
\hfill k & I & 0 \cr
...
...rmatrix{ & k & l \cr
\hfill l & 0 & S \cr
p-l & 0 & 0 } \; .
\end{displaymath}

Here l is the rank of B, k=r-l, C and S are diagonal matrices satisfying C2 + S2 = I, and S is nonsingular. We may also identify $\alpha_1 = \cdots = \alpha_k = 1$ , $\alpha_{k+i} = c_{ii}$ for $i=1, \ldots , l$ , $\beta_1 = \cdots = \beta_k = 0$ , and $\beta_{k+i} = s_{ii}$ for $i=1, \ldots , l$ . Thus, the first k generalized singular values $\alpha_1 / \beta_1 , \ldots , \alpha_k / \beta_k$ are infinite, and the remaining l generalized singular values are finite.

In the second case, when m-r < 0,

\begin{displaymath}
\Sigma_1 = \bordermatrix{ & k & m-k & k+l-m \cr
\hfill k & I & 0 & 0 \cr
m-k & 0 & C & 0 }
\end{displaymath}

and

\begin{displaymath}
\Sigma_2 = \bordermatrix{ & k & m-k & k+l-m \cr
\hfill m-k ...
... & 0 \cr
k+l-m & 0 & 0 & I \cr
\hfill p-l & 0 & 0 & 0 } \; .
\end{displaymath}

Again, l is the rank of B, k=r-l, C and S are diagonal matrices satisfying C2 + S2 = I, S is nonsingular, and we may identify $\alpha_1 = \cdots = \alpha_k = 1$ , $\alpha_{k+i} = c_{ii}$ for $i=1, \ldots , m-k$ , $\alpha_{m+1} = \cdots = \alpha_r = 0$ , $\beta_1 = \cdots = \beta_k = 0$ , $\beta_{k+i} = s_{ii}$ for $i=1, \ldots , m-k$ , and $\beta_{m+1} = \cdots = \beta_r = 1$ . Thus, the first k generalized singular values $\alpha_1 / \beta_1 , \ldots , \alpha_k / \beta_k$ are infinite, and the remaining l generalized singular values are finite.

Here are some important special cases of the generalized singular value decomposition. First, if B is square and nonsingular, then r=n and the generalized singular value decomposition of A and B is equivalent to the singular value decomposition of AB-1, where the singular values of AB-1 are equal to the generalized singular values of the pair A, B:

\begin{displaymath}
AB^{-1} = (U \Sigma_1 R Q^T)(V \Sigma_2 R Q^T)^{-1} =
U ( \Sigma_1 \Sigma_2^{-1} ) V^T \; \; .
\end{displaymath}

Second, if the columns of $(A^T \; B^T)^T$ are orthonormal, then r=n, R=I and the generalized singular value decomposition of A and B is equivalent to the CS (Cosine-Sine) decomposition of $(A^T \; B^T)^T$ [55]:

\begin{displaymath}
\left( \begin{array}{c} A \\ B \end{array} \right) = \left( ...
...array}{c} \Sigma_1 \\ \Sigma_2 \end{array} \right) Q^T \; \; .
\end{displaymath}

Third, the generalized eigenvalues and eigenvectors of $A^TA - \lambda B^TB$ can be expressed in terms of the generalized singular value decomposition: Let

\begin{displaymath}
X = Q \left( \begin{array}{cc} I & 0 \\ 0 & R^{-1} \end{array} \right) \; \; .
\end{displaymath}

Then

\begin{displaymath}
X^T A^T A X = \left( \begin{array}{cc}
0 & 0 \\
0 & \Sigm...
...{cc}
0 & 0 \\
0 & \Sigma^T_2 \Sigma_2
\end{array} \right).
\end{displaymath}

Therefore, the columns of X are the eigenvectors of $A^TA - \lambda B^TB$ , and the ``nontrivial'' eigenvalues are the squares of the generalized singular values (see also section 2.3.5.1). ``Trivial'' eigenvalues are those corresponding to the leading n-r columns of X, which span the common null space of AT A and BT B. The ``trivial eigenvalues'' are not well defined2.1.

A single driver routine xGGSVD computes the generalized singular value decomposition of A and B (see Table 2.6). The method is based on the method described in [83,10,8].


Table 2.6: Driver routines for generalized eigenvalue and singular value problems
Type of Function and storage scheme Single precision Double precision
problem   real complex real complex
GSEP simple driver SSYGV CHEGV DSYGV ZHEGV
  divide and conquer driver SSYGVD CHEGVD DSYGVD ZHEGVD
  expert driver SSYGVX CHEGVX DSYGVX ZHEGVX
  simple driver (packed storage) SSPGV CHPGV DSPGV ZHPGV
  divide and conquer driver SSPGVD CHPGVD DSPGVD ZHPGVD
  expert driver SSPGVX CHPGVX DSPGVX ZHPGVX
  simple driver (band matrices) SSBGV CHBGV DSBGV ZHBGV
  divide and conquer driver SSBGVD CHBGVD DSBGV ZHBGVD
  expert driver SSBGVX CHBGVX DSBGVX ZHBGVX
GNEP simple driver for Schur factorization SGGES CGGES DGGES ZGGES
  expert driver for Schur factorization SGGESX CGGESX DGGESX ZGGESX
  simple driver for eigenvalues/vectors SGGEV CGGEV DGGEV ZGGEV
  expert driver for eigenvalues/vectors SGGEVX CGGEVX DGGEVX ZGGEVX
GSVD singular values/vectors SGGSVD CGGSVD DGGSVD ZGGSVD


next up previous contents index
Next: Computational Routines Up: Generalized Eigenvalue and Singular Previous: Generalized Nonsymmetric Eigenproblems (GNEP)   Contents   Index
Susan Blackford
1999-10-01