Unit3.3.3Practical computation of the Householder vector

Subsubsection3.3.3.1The 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{.}$)

Subsubsection3.3.3.2The 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{.}$

Subsubsection3.3.3.3A 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{.}$