5
$\begingroup$

Suppose I have $A=A_nA_{n-1}\cdots A_2A_1$

How can I compute the $QR$ factorization of $A$ without explicitly multiplying $A_1, A_2, \ldots, A_n$ together?

The suggestion I got is that, suppose $n=3$ and $Q_3^T A =R$

The write $$Q_3^T A =Q_3^T A_3Q_2Q_2^T A_2Q_1Q_1^T A_1Q_0, Q_0=I$$

Then find orthogonal $Q_i$ such that $Q_i^T A_iQ_{i-1}$ is upper triangular.

$\endgroup$
  • 1
    $\begingroup$ As you said, you can find the QR factorization of $A$ by successively finding $Q_i$ such that $Q_i^TA_iQ_{i-1}$ is upper triangular, which will express the resulting R-factor as a product of $n$ R-factors. Nevertheless, you have to apply $Q_{i-1}$ to $A_i$ first at each step. $\endgroup$ – Algebraic Pavel Mar 4 '15 at 12:35
  • $\begingroup$ Are all the $A_i$ square matrices, or can they be rectangular? $\endgroup$ – Victor Liu Mar 6 '15 at 0:50
  • $\begingroup$ Interesting question, but for the benefit of assessing answers, what would be the objective of doing so? Is it indeed to keep condition number in check as @VictorLiu mentions? Are you looking for some cool pure-math approach or do you have system constraints that require something of you? (i.e. less computations, less memory usage, etc.). $\endgroup$ – Mefitico Jan 11 at 13:33
0
$\begingroup$

The main reason to compute the QR factorization of the product rather than multiplying them all together is to keep the condition numbers in check. It is not more efficient (nor is it substantially less efficient computationally due to good cache utilization in modern QR implementations).

You compute $A_1 = QR$, then apply $Q^T$ from the right to $A_2$, then repeat until you get to $A_n$. In summary:

tmp = A_1
for i = 1 to n
    [Q,R_i] = qr(tmp);
    tmp = A_{i+1} * Q^T
end
R = R_n * R_{n-1} * ... * R_1

The last $Q$ computed is the $Q$ of the product, and the product of all the intermediate $R$ matrices is the $R$ of the product.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.