# QR factorization: Givens rotations vs. Householder reflections

Here is the algorithm for Housholder $QR$ factorization:

$A$ is a $m \times n$ matrix and $m$ is greater than $n$.

$For \quad k=1 \quad to \quad n$

$\quad x = A_{k:m,k}$

$\quad v_{k} = sign(x_{1})||x||_{2}e_{1} + x$

$\quad v_{k} =\frac {v_{k}} {||v_{k}||_2}$

$\quad A_{k:m,k:n}= A_{k:m,k:n} - 2v_{k}( v_{k}^{*} A_{k:m,k:n})$

$End$

Then the following code is a $QR$ factorization algorithm and it is analog to algorithm above but it uses the rotation matrices $F$ and $J$ instead of Householder reflections. $$F = \begin{bmatrix}-c&s \\ s&c \end{bmatrix}$$ $$J= \begin{bmatrix}c&s\\ -s&c \end{bmatrix}$$ $$s = sin(\theta)$$ $$c = cos(\theta)$$ $\theta$ is the angle between a vector and $x$-axis.

$For \quad j=1:n$

$\quad For \quad i=m:-1:j+1$

$\quad \quad a = A(i-1,j)$

$\quad \quad b =A(i,j)$

$\quad \quad c = \frac{a}{\sqrt{(a^2+b^2)}} % c = cos(\theta)$

$\quad \quad s = \frac{b}{\sqrt{(a^2+b^2)}} % s = sin(\theta)$

$\quad \quad A(i-1:i,j:n)=\begin{bmatrix}c&-s \\ s&c \end{bmatrix}*A(i-1:i,j:n);$

$\quad End$

$End$

I cannot really follow the logic of the second algorithm. How it is mapped to the first algorithm or even $QR$ factorization? Does anyone have any insights?

Thanks.

• It is the Francis algorithm for which there is an abundant litterature. See for example (dm.unibo.it/~guerrini/html/an_09_10/QR_50_years_later.pdf) – Jean Marie Aug 20 '16 at 22:30
• Thank you. I did not know the name. – Crimson Aug 20 '16 at 22:32
• See also Givens rotation. – hardmath Aug 21 '16 at 15:27
• @hardmath Thanks. I am actually working on Given rotation in Matrix Computation book. Trying to understand. – Crimson Aug 21 '16 at 15:30
• The short answer is a Givens rotation allows us to zero out one entry below the diagonal, while a Householder reflection can zero out all the subdiagonal entries in a column. If it would be of interest, I can sketch out some of the trade-offs in using one approach vs. the other in an Answer. – hardmath Aug 22 '16 at 3:04