I am struggling to find a reference for this: In terms of big Oh notation does anyone know of any expressions for the computational time taken by commonly used algorithms for QR decompositions?


Wikipedia says the complexity is $O(n^3)$ floating point multiplication operations when using Householder reflections.

The following table gives the number of operations in the $k$-th step of the QR-decomposition by the Householder transformation, assuming a square matrix with size $n$.

$$\begin{array}{c|c|} \text{Operation} & \text{Number of operations in $k$th step} \\ \hline \text{Multiplications} & 2(n-k+1)^2 \\ \hline \text{Additions} & (n-k+1)^2 + (n-k+1)(n-k)+2 \\ \hline \text{Divisions} & 1 \\ \hline \text{Square Root} & 1 \\ \hline \end{array}$$

Summing these numbers over the $n-1$ steps (for a square matrix of size $n$), the complexity of the algorithm (in terms of floating point multiplications) is given by

$$ \frac{2}{3}n^3 + n^2+\frac{1}{3}n-2=O(n^3) $$

Surprisingly, I haven't found a complexity analysis for QR factorization stated in Golub & van Loan. Weird.

| cite | improve this answer | |

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.