Solved – QR decomposition computational efficiency

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.

Similar Posts:

Rate this post

Leave a Comment