next up previous contents index
Next: Symmetric Eigenproblems Up: Generalized Orthogonal Factorizations and Previous: Generalized QR Factorization   Contents   Index

Generalized RQ Factorization

The generalized RQ (GRQ) factorization of an m-by-n matrix A and a p-by-n matrix B is given by the pair of factorizations

\begin{displaymath}
A = R Q \quad \mbox{and} \quad B = Z T Q
\end{displaymath}

where Q and Z are respectively n-by-n and p-by-p orthogonal matrices (or unitary matrices if A and B are complex). R has the form

\begin{displaymath}
R = \bordermatrix{ & n-m & m \cr
m & 0 & R_{12} }, \quad \mbox{if} \quad m \leq n
\end{displaymath}

or

\begin{displaymath}
R = \bordermatrix{ & n \cr
m-n & R_{11} \cr
\hfill n & R_{21} }, \quad \mbox{if} \quad m > n,
\end{displaymath}

where R12 or R21 is upper triangular. T has the form

\begin{displaymath}
T = \bordermatrix{ & n \cr
\hfill n & T_{11} \cr
p-n & 0 }, \quad \mbox{if} \quad p \geq n
\end{displaymath}

or

\begin{displaymath}
T = \bordermatrix{ & p & n-p \cr
p & T_{11} & T_{12} }, \quad \mbox{if} \quad p < n
\end{displaymath}

where T11 is upper triangular.

Note that if B is square and nonsingular, the GRQ factorization of A and B implicitly gives the RQ factorization of the matrix AB-1:

A B-1 = ( R T-1 ) ZT

without explicitly computing the matrix inverse B-1 or the product AB-1.

The routine xGGRQF computes the GRQ factorization by first computing the RQ factorization of A and then the QR factorization of BQT. The orthogonal (or unitary) matrices Q and Z can either be formed explicitly or just used to multiply another given matrix in the same way as the orthogonal (or unitary) matrix in the RQ factorization (see section 2.4.2).

The GRQ factorization can be used to solve the linear equality-constrained least squares problem (LSE) (see (2.2) and [55, page 567]). We use the GRQ factorization of B and A (note that B and A have swapped roles), written as

\begin{displaymath}
B = T Q \quad \mbox{and} \quad A = Z R Q.
\end{displaymath}

We write the linear equality constraints Bx = d as:

T Q x = d

which we partition as:

\begin{displaymath}
\bordermatrix{ & n-p & p \cr
p & 0 & T_{12} }
\left( \begin...
...t( \begin{array}{c} x_1 \\ x_2 \end{array} \right) \equiv Q x.
\end{displaymath}

Therefore x2 is the solution of the upper triangular system

T12 x2 = d

Furthermore,

\begin{eqnarray*}
\Vert A x - c \Vert _2 & = & \Vert Z^T A x - Z^T c \Vert _2 \\
& = & \Vert R Q x - Z^T c \Vert _2.
\end{eqnarray*}


We partition this expression as:

\begin{displaymath}
\bordermatrix{ & n-p & p \cr
\hfill n-p & R_{11} & R_{12} \...
...ght) - \left( \begin{array}{c} c_1 \\ c_2 \end{array} \right)
\end{displaymath}

where $\left( \begin{array}{c} c_1 \\ c_2 \end{array} \right) \equiv Z^T c$, which can be computed by xORMQR (or xUNMQR).

To solve the LSE problem, we set

R11 x1 + R12 x2 - c1 = 0

which gives x1 as the solution of the upper triangular system

R11 x1 = c1 - R12 x2.

Finally, the desired solution is given by

\begin{displaymath}
x = Q^T \left( \begin{array}{c} x_1 \\ x_2 \end{array} \right) ,
\end{displaymath}

which can be computed by xORMRQ (or xUNMRQ).


next up previous contents index
Next: Symmetric Eigenproblems Up: Generalized Orthogonal Factorizations and Previous: Generalized QR Factorization   Contents   Index
Susan Blackford
1999-10-01