Past exam of the numerical linear algebra course of the University of Oxford / 2025 / 3 / a / ii / Solution

For the small QR decomposition, each of the $k$ Givens rotations eliminates one subdiagonal entry of the upper Hessenberg matrix. At column $j$, apply the rotation to two rows in columns $j,\dots ,k$, costing $O(k-j+1)$ arithmetic operations. Summing gives $O(k^2)$, and applying the rotations to the right-hand side costs $O(k)$. Backward substitution in a triangular system costs $O(k^2)$.

Computing $\Vert b{\Vert }_2$ costs $O(n)$ and the final dense matrix multiplication $Q_k{y}_k$ costs $O(nk)$. Thus the total, with the Arnoldi decomposition already supplied, isHere $1\le k<n$, since $Q_{k+1}$ has orthonormal columns in ${\mathbb{R}}^n$. In the standard dense arithmetic model, forming the general matrix–vector product gives the sharp $\Theta (nk)$ cost. The pair above records that two-parameter bound; looser bounds such as $O(n^2)$ are also possible because $k<n$. Treating ${\tilde{H}}_k$ as an unstructured dense matrix would unnecessarily replace its $O(k^2)$ factorization by an $O(k^3)$ computation.