Skip to main content

Subsection 4.4.3 Via 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.

login