QR decomposition subcases

Question

Is the full QR decomposition the most general, which includes the reduced QR, i.e, is it alright to always compute the full QR Decomposition for a given matrix blindly? What's the point of having two different QR decompositions? Please tell me all the possible ways of finding the QR factorization using the Gram-Schmidt Process, if using the full decomposition always is wrong.

Answer 1

First of all, yes, any matrix $A \in \mathcal{M}_{mn}(\mathbb{K})$ can be decomposed in that pattern. Note that $Q$ and $R$ are not unique. However, you seem to misinterpret the role of the Gram-Schmidt process in the computation of the QR decomposition.

Please tell me all the possible ways of finding the QR factorization using the Gram-Schmidt Process, if using the full decomposition always is wrong.

Your question is a bit vague. A QR decomposition can always be computed on any matrix you want, and the Gram-Schmidt process (GSP) is only one way to compute it. It's a "full decomposition" in itself, but it will lead to a different decomposition compared to another method. Therefore there is no such thing as a global decomposition, as you seem to think, but rather several ones. They are all theoretically equivalent but the methods practically differ in terms of numerical stability.

The main drawback of the GSP is that it tends to be — very — numerically unstable, notably because you may have to divide by small numbers during the orthogonalisation process. It requires $mn^2$ multiplications.

The two other main methods should be preferred. I won't describe how they work in details since the web is already full of great articles and implementations of these algorithms.

• the Householder process, where $Q$ is obtained by successive elementary matrices multiplications, is much more stable, with an acceptable cost of $mn^2 − \frac{n^3}{3}$ multiplications;
• the Givens process, where $Q$ is obtained by successive multiplications of rotation matrices, even more stable than Householder, but requires $2mn^2 − \frac{2n^3}{3}$ multiplications.

Definitely, a proper linear algebra library will use one of these two methods but never Gram-Schmidt.