## Subsection4.4.3Via the Householder QR factorization

Given $A \in \Cmxn$ with linearly independent columns, the Householder QR factorization yields $n$ Householder transformations, $H_0, \ldots, H_{n-1} \text{,}$ so that

\begin{equation*} \begin{array}[t]{c} \underbrace{H_{n-1} \cdots H_0}\\ Q^H \end{array} A = \FlaTwoByOne{ R_{TL} }{ 0 }. \end{equation*}

$[ A, t ] = {\rm HouseQR\_unb\_var1}( A )$ overwrites $A$ with the Householder vectors that define $H_0, \cdots , H_{n-1}$ below the diagonal and $R_{TL}$ in the upper triangular part.

Rather than explicitly computing $Q$ and then computing $\widetilde y := Q^H y \text{,}$ we can instead apply the Householder transformations:

\begin{equation*} \widetilde y := H_{n-1} \cdots H_0 y, \end{equation*}

overwriting $y$ with $\widehat y \text{.}$ After this, the vector $y$ is partitioned as $y = \FlaTwoByOne{ y_T }{ y_B}$ and the triangular system $R_{TL} \hat x = y_T$ yields the desired solution.

The steps and theirs costs of this approach are

• From Subsection 3.3.4, factoring $A = Q R$ via the Householder QR factorization costs, approximately, $2 mn^2 - \frac{2}{3} n^3$ flops.

• From Homework 3.3.6.1, applying $Q$ as a sequence of Householder transformations costs, approximately, $4 m n - 2 n^2$ flops.

• Solve $R_{TL} \hat x = y_T \text{:}$ $n^2$ flops.

Total: $2 m n^2 - \frac{2}{3} n^3 + 4 m n - n^2 \approx 2 m n^2 - \frac{2}{3} n^3$ flops.