What is the operation count for QR factorization using Householder transformations? I have a hard time finding the operation count of QR factorization when using Householder transformations. The answer is $2mn^2 - \frac{2n^3}{3}$, but have no clue on how to get this count following some procedure. 
Could anyone help me go through this step by step?
 A: Suppose you have a $m \times n$ matrix $A$, $m \geq n$, and you want to perform QR factorization using Householder transformations. 
You will have to go through $A$ as follows: 


*

*Start with the whole matrix

*Proceed with the modified matrix of original size without it's first row and first column.

*Proceed with second modified matrix without first two rows and columns. 

*And so on...


In a more compact way this is stated as $A_{k:m,k:n}$ for every iteration step $k$. Now the (part of the) algorithm (which does most of the work) can be denoted similarly, i.e. per iteration you have $A_{k:m,k:n} =  A_{k:m,k:n} - 2v_k (v_{k}^TA_{k:m,k:n})$.
Now the operation you want to count are in these iterations. Per iteration you have:


*

*$(m-k)(n-k)$ for the outer product $2v_k(\dots)$

*$2(m-k)(n-k)$ for the products $v_{k}^TA_{k:m,k:n}$

*$(m-k)(n-k)$ for the subtraction $A_{k:m,k:n} - \dots$


So that is $4(m-k)(n-k)$ in total. Which you do for every iteration (!), so you get
$\sum\limits_{k=1}^{n} 4(m-k)(n-k) =4 \sum\limits_{k=1}^{n} (mn-k(m+n)+k^2)$ 
$\approx 4mn^2 - 4(m+n)n^2/2 + 4n^3/3 = 2mn^2-2n^3/3$
