Skip to main content

Subsection 10.2.6 Cost 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!