Symmetric and unsymmetric QR iteration

We compare the computational cost of performing the QR iteration on unsymmetric vs symmetric matrices. As we expect, the symmetric case is significantly faster.

Unsymmetric §

• Cost of upper Hessenberg form: $O(n^3)$
• QR iteration step: cost $O(n^2)$ using Givens transformations.

Symmetric §

• Cost of upper Hessenberg form: $O(n^3)$

From $Q^{T}AQ=H$, we get that $H$ is symmetric. So $H$ is Hessenberg and symmetric. So it is tri-diagonal symmetric.

Consider now the steps in the QR iteration. Recall that

$$T_{k+1}=U_{k+1}^H{T}_k{U}_{k+1}.$$

So $T_k$ remains symmetric. It is also upper Hessenberg, so it remains tri-diagonal symmetric.

• The cost of each QR iteration step is just $O(n)$.
• The first step is expensive, but after that, each iteration is extremely cheap.