3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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) $\endgroup$ – Jean Marie Aug 20 '16 at 22:30
  • $\begingroup$ Thank you. I did not know the name. $\endgroup$ – Crimson Aug 20 '16 at 22:32
  • 1
    $\begingroup$ See also Givens rotation. $\endgroup$ – hardmath Aug 21 '16 at 15:27
  • $\begingroup$ @hardmath Thanks. I am actually working on Given rotation in Matrix Computation book. Trying to understand. $\endgroup$ – Crimson Aug 21 '16 at 15:30
  • 1
    $\begingroup$ 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. $\endgroup$ – hardmath Aug 22 '16 at 3:04

Your Answer

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

Browse other questions tagged or ask your own question.