Skip to main content

Subsection 3.3.3 Practical computation of the Householder vector

Subsubsection 3.3.3.1 The real case

Next, we discuss a slight variant on the above discussion that is used in practice. To do so, we view \(x \) as a vector that consists of its first element, \(\chi_1 \text{,}\) and the rest of the vector, \(x_2 \text{:}\) More precisely, partition

\begin{equation*} x = \left( \begin{array}{c} \chi_1 \\ \hline x_2 \end{array} \right), \end{equation*}

where \(\chi_1 \) equals the first element of \(x \) and \(x_2 \) is the rest of \(x \text{.}\) Then we will wish to find a Householder vector \(u = \FlaTwoByOneSingleLine { 1 } { u_2 }\) so that

\begin{equation*} \left( I - \frac{1}{\tau} \FlaTwoByOneSingleLine { 1 } { u_2 } \FlaTwoByOneSingleLine { 1 } { u_2 }^T \right) \FlaTwoByOneSingleLine { \chi_1 } { x_2 } = \FlaTwoByOneSingleLine { \pm \| x \|_2 } { 0 }. \end{equation*}

Notice that \(y \) in the previous discussion equals the vector \(\FlaTwoByOneSingleLine { \pm \| x \|_2 } { 0 }\text{,}\) so the direction of \(u \) is given by

\begin{equation*} v = \FlaTwoByOneSingleLine { \chi_1 \mp \| x \|_2 } { x_2 }. \end{equation*}

We now wish to normalize this vector so its first entry equals "1":

\begin{equation*} u = \frac{v}{\nu_1} = \frac{1} { \chi_1 \mp \| x \|_2 } \FlaTwoByOneSingleLine { \chi_1 \mp \| x \|_2 } { x_2 } = \FlaTwoByOneSingleLine { 1 } { x_2 / \nu_1 }. \end{equation*}

where \(\nu_1 = \chi_1 \mp \| x \|_2 \) equals the first element of \(v \text{.}\) (Note that if \(\nu_1 = 0 \) then \(u_2 \) can be set to \(0 \text{.}\))

Subsubsection 3.3.3.2 The complex case (optional)

Let us work out the complex case, dealing explicitly with \(x \) as a vector that consists of its first element, \(\chi_1 \text{,}\) and the rest of the vector, \(x_2 \text{:}\) More precisely, partition

\begin{equation*} x = \left( \begin{array}{c} \chi_1 \\ \hline x_2 \end{array} \right), \end{equation*}

where \(\chi_1 \) equals the first element of \(x \) and \(x_2 \) is the rest of \(x \text{.}\) Then we will wish to find a Householder vector \(u = \FlaTwoByOneSingleLine { 1 } { u_2 }\) so that

\begin{equation*} \left( I - \frac{1}{\tau} \FlaTwoByOneSingleLine { 1 } { u_2 } \FlaTwoByOneSingleLine { 1 } { u_2 }^H \right) \FlaTwoByOneSingleLine { \chi_1 } { x_2 } = \FlaTwoByOneSingleLine { \complexone \| x \|_2 } { 0 }. \end{equation*}

Here \(\complexone \) denotes a complex scalar on the complex unit circle. By the same argument as before

\begin{equation*} v = \FlaTwoByOneSingleLine { \chi_1 - \complexone \| x \|_2 } { x_2 }. \end{equation*}

We now wish to normalize this vector so its first entry equals "1":

\begin{equation*} u = \frac{v}{\nu_1} = \frac{1} { \chi_1 - \complexone \| x \|_2 } \FlaTwoByOneSingleLine { \chi_1 - \complexone \| x \|_2 } { x_2 } = \FlaTwoByOneSingleLine { 1 } { x_2 / \nu_1 }. \end{equation*}

where \(\nu_1 = \chi_1 - \complexone \| x \|_2 \text{.}\) (If \(\nu_1 = 0 \) then we set \(u_2 \) to \(0 \text{.}\))

As was the case for the real-valued case, the choice \(\complexone \) is important. We choose \(\complexone = - \sign( \chi_1 ) = - \frac{\chi_1}{\vert \chi_1 \vert} \text{.}\)

Subsubsection 3.3.3.3 A routine for computing the Householder vector

The vector

\begin{equation*} \FlaTwoByOneSingleLine{1}{u_2} \end{equation*}

is the Householder vector that reflects \(x \) into \(\complexone \| x \|_2 e_0 \text{.}\) The notation

\begin{equation*} \left[ \FlaTwoByOneSingleLine {\rho} { u_2}, \tau \right] := {\rm Housev} \left( \FlaTwoByOneSingleLine { \chi_1 } { x_2 } \right) \end{equation*}

represents the computation of the above mentioned vector \(u_2 \text{,}\) and scalars \(\rho \) and \(\tau \text{,}\) from vector \(x \text{.}\) We will use the notation \(H(x) \) for the transformation \(I - \frac{1}{\tau} u u^H \) where \(u \) and \(\tau \) are computed by \({\rm Housev}( x ) \text{.}\)

\begin{equation*} \begin{array}{|l|} \hline {\rm Algorithm:~} \left[ \FlaTwoByOneSingleLine {\rho} {u_2} , \tau \right] = {\rm Housev} \left( \FlaTwoByOneSingleLine {\chi_1} {x_2} \right) \\ \hline \begin{array}{l | l} \amp \chi_2 := \| x_2 \|_2 \\ \amp \alpha := \left\| \left( \begin{array}{c} \chi_1 \\ \chi_2 \end{array} \right) \right\|_2 (= \| x \|_2) \\ \rho = - \sign( \chi_1 ) \| x \|_2 \amp \rho := - \sign( \chi_1 ) \alpha \\ \nu_1 = \chi_1 + \sign( \chi_1 ) \| x \|_2 \amp \nu_1 := \chi_1 - \rho \\ u_2 = x_2 / \nu_1 \amp u_2 := x_2 / \nu_1 \\ \amp \chi_2 = \chi_2 / \vert \nu_1 \vert ( = \| u_2 \|_2 ) \\ \tau = ( 1 + u_2^H u_2 ) / 2 \amp \tau = ( 1 + \chi_2^2 ) / 2 \end{array} \\ \hline \end{array} \end{equation*}
Figure 3.3.3.1. Computing the Householder transformation. Left: simple formulation. Right: efficient computation. Note: I have not completely double-checked these formulas for the complex case. They work for the real case.
Remark 3.3.3.2.

The function 

function [ rho, ... 
            u2, tau ] = Housev( chi1, ... 
                                 x2 )

1implements the function Housev. It can be found in Assignments/Week03/matlab/Housev.m

login