Subsection10.2.6Cost of a simple QR algorithm

The QR algorithms that we have discussed incur the following costs for an $m \times m$ Hermitian matrix:

• $A \rightarrow Q R$ (QR factorization) Approximate cost: $4/3 m^3$ flops.

• $A := R Q \text{.}$ A naive implementation would take advantage of $R$ being upper triangular, but not of the fact that $A$ will again be Hermitian. The approximate cost then equals $m^3$ flops. If one also takes advantage of the fact that $A$ is Hermitian, that cost is reduced to, approximately, $1/2 m^3$ flops.

• If the eigenvectors are desired, the update $V := V Q$ requires approximately $2 m^3$ flops.

Any other costs, like shifting the matrix, are inconsequential.

Thus, the cost, per iteration, equals approximately $(\frac{4}{3} + \frac{1}{2} m^3 = \frac{11}{6} m^3$ flops if only the eigenvalues are to be computed. If the eigenvalues are also required, then the cost increases by $2 m^3$ flops to become $\frac{23}{6} m^3$ flops.

Let us now consider adding deflation. The rule of thumb is that it takes a few iterations per eigenvalue that is found. Let's say $K$ iterations are need. Ever time an eigenvalue is found, the problem deflates, decreasing in size by one. The cost then becomes

\begin{equation*} \sum_{i=m}^{1} K \frac{23}{6} i^3 \approx K \frac{23}{6} \int_{0}^{m} x^3 dx = K \frac{23}{6} \frac{1}{4} x^4 \vert_0^m =K \frac{23}{24} m^4. \end{equation*}

The bottom line is that the computation requires $O(m^4)$ flops. All other factorizations we have encountered so far require $O^(m^3)$ flops. Generally $O^(m^4)$ is considered impractally costly. We need to do better!