4
$\begingroup$

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?

$\endgroup$

2 Answers 2

5
$\begingroup$

If I've counted correctly, in general, QR decomposition on a matrix $A \in \mathbb{R}^{m \times n}$ should be $\mathcal{O}(d^2D)$ flops using the Householder method, where $D = \max\{m,n\}$ and $d = \min\{m,n\}$.

Why, the actual matrix $R$ in question is $R = H_K \cdots H_1 A$ where $K=\min\{m-1,n\}$ and each $H_k$ is a Householder matrix. However, multiplying $HB$ is relatively easy (compared to generic matrix multiplication) when $H = I - 2uu^T$.

Indeed, we can first compute $v = B^Tu$ in $\mathcal{O}(mn)$ flops. Second, we can recover $2uu^TB$ as $M = 2uv^T$ in exactly $2mn$ multiplications. Finally, we just need to subtract $B-M$ in exactly $mn$ subtractions. Thus, the cost of computing the matrix product $HB$ is $\mathcal{O}(mn) + 2mn + mn = \mathcal{O}(mn)$.

We need to do this $K \leq d$ times (the $k$-th time using the already computed $B = H_{k-1}\cdots H_1 A$) hence the total complexity is $d\mathcal{O}(mn) = \mathcal{O}(dmn) = \mathcal{O}(d^2D)$ where the final equality holds upon noticing the cute fact that $mn = dD$.

The matrix $Q$ itself is just $Q=H_K \cdots H_1$. The flops required for computing this matrix can be counted by applying the previous reasoning, too.

$\endgroup$
6
$\begingroup$

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) $$

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.