up


Householder Method for Tridiagonalization: Ver. 1.0

Taisuke Ozaki, RCIS, JAIST

The Householder method [1] is a way of transforming a Hermitian matrix $B$ to a real symmetric tridiagonalized matrix $B_{\rm TD}$. Let ${\bf b}$ be a column vector of $B$, and consider that the vector ${\bf b}$ consists of the real part ${\bf b}_r$ and the imaginary part ${\bf b}_i$ as
    $\displaystyle \vert {\bf b} \rangle = \vert {\bf b}_r \rangle
+ i \vert {\bf b}_i \rangle.$ (1)

Also let us introduce a vector ${\bf s}$ of which real part has just one non-zero component $s(=\sqrt{\langle {\bf b} \vert {\bf b} \rangle})$ and imaginary part is a zero vector as
    $\displaystyle \vert {\bf s} \rangle =
\left(
\begin{array}{c}
s\\
0\\
\cdot\\...
...)
+ i
\left(
\begin{array}{c}
0\\
0\\
\cdot\\
\cdot\\
0
\end{array}\right).$ (2)

Then, consider a mirror transform $Q^{\dag }$ bridging the two vectors ${\bf b}$ and ${\bf s}$ by
    $\displaystyle Q^{\dag } = I - \alpha^{*}\vert {\bf v} \rangle \langle {\bf v} \vert,$ (3)

where let us assume that
    $\displaystyle \vert {\bf s} \rangle = Q^{\dag }\vert {\bf b} \rangle.$ (4)

Putting Eq. (3) into Eq. (4), and solving it with respect to $\vert {\bf v} \rangle$, we have
    $\displaystyle \vert {\bf v} \rangle =
\frac{1}{\alpha^* \langle {\bf v}\vert {\bf b} \rangle}
\left(
\vert {\bf b} \rangle - \vert {\bf s} \rangle
\right).$ (5)

Thus, Eq. (5) allows us to write $\vert {\bf v} \rangle$ as
    $\displaystyle \vert {\bf v} \rangle =
\beta
\left(
\vert {\bf b} \rangle - \vert {\bf s} \rangle
\right)
= \beta \vert {\bf u} \rangle.$ (6)

If ${\bf v}$ is normalized, $\beta$ is given by
$\displaystyle \beta$ $\textstyle =$ $\displaystyle \frac{1}{\sqrt{(\langle {\bf b} \vert - \langle {\bf s} \vert)
(\vert {\bf b} \rangle - \vert {\bf s} \rangle)}},$  
  $\textstyle =$ $\displaystyle \frac{1}{\sqrt{\langle {\bf b} \vert {\bf b} \rangle
+\langle {\b...
...langle {\bf b} \vert {\bf s} \rangle
-\langle {\bf s} \vert {\bf b} \rangle
}},$  
  $\textstyle =$ $\displaystyle \frac{1}{\sqrt{ 2s^2
-\langle {\bf b} \vert {\bf s} \rangle
-\langle {\bf s} \vert {\bf b} \rangle
}}.$ (7)

Comparing Eqs. (5) with (6) and making use of Eq. (7), we have
    $\displaystyle \alpha^*
= \frac{2a_r}{a_r^2+a_i^2}(a_r - ia_i)$ (8)

with $a_r$ and $a_i$ given by
    $\displaystyle a_r = \frac{1}{2}\left(
2s^2-\langle {\bf b} \vert {\bf s} \rangle
-\langle {\bf s} \vert {\bf b} \rangle \right)$ (9)

and
    $\displaystyle a_i = \langle {\bf b}_i \vert {\bf s} \rangle.$ (10)

Then, it is verified that
$\displaystyle QQ^{\dag }$ $\textstyle =$ $\displaystyle \left(
I - \alpha\vert {\bf v} \rangle \langle {\bf v} \vert
\right)
\left(
I - \alpha^{*}\vert {\bf v} \rangle \langle {\bf v} \vert
\right),$  
  $\textstyle =$ $\displaystyle I - \alpha^{*}\vert {\bf v} \rangle \langle {\bf v} \vert
- \alph...
...rt {\bf v} \rangle \langle {\bf v}
\vert {\bf v} \rangle \langle {\bf v} \vert,$  
  $\textstyle =$ $\displaystyle I -\frac{(2a_r)^2}{a_r^2+a_i^2} \vert {\bf v} \rangle \langle {\b...
...vert
+\frac{(2a_r)^2}{a_r^2+a_i^2} \vert {\bf v} \rangle \langle {\bf v} \vert,$  
  $\textstyle =$ $\displaystyle I.$ (11)

Thus, the transformation $Q^{\dag }BQ$ for the Hermitian matrix $B$ is a similarity transformation, and given by
$\displaystyle Q^{\dag }BQ$ $\textstyle =$ $\displaystyle \left(
I - \alpha^*\vert {\bf v} \rangle \langle {\bf v} \vert
\right)
B
\left(
I - \alpha\vert {\bf v} \rangle \langle {\bf v} \vert
\right),$  
  $\textstyle =$ $\displaystyle B - \alpha^*\vert {\bf v} \rangle \langle {\bf v} \vert B
- \alph...
...v} \rangle \langle {\bf v} \vert B
\vert {\bf v} \rangle \langle {\bf v} \vert.$ (12)

By defining
    $\displaystyle \vert {\bf p} \rangle \equiv B\vert {\bf v} \rangle,$ (13)

Eq. (12) becomes
$\displaystyle Q^{\dag }BQ$ $\textstyle =$ $\displaystyle B - \alpha^*\vert {\bf v} \rangle \langle {\bf p}
- \alpha \vert ...
...rt {\bf v} \rangle \langle {\bf v}
\vert {\bf p} \rangle \langle {\bf v} \vert,$  
  $\textstyle =$ $\displaystyle B -\alpha^* \vert {\bf v} \rangle
\left(
\langle {\bf p} \vert
-\...
...v} \rangle
\langle {\bf v} \vert {\bf p} \rangle
\right)
\langle {\bf v} \vert.$ (14)

Moreover, by defining
    $\displaystyle \vert {\bf q} \rangle
\equiv
\alpha
\left(
\vert {\bf p} \rangle
...
...alpha^*}{2}\vert {\bf v} \rangle
\langle {\bf v} \vert {\bf p} \rangle
\right),$ (15)

we have a compact form:
    $\displaystyle Q^{\dag }BQ
=
B - \vert {\bf v} \rangle \langle {\bf q} \vert
- \vert {\bf q} \rangle \langle {\bf v} \vert.$ (16)

For the numerical stability, we furthermore modify Eq. (16) as shown below. Let us introduce a vector ${\bf p}'$ as.
    $\displaystyle \vert {\bf p}' \rangle
=
\frac{B\vert {\bf u} \rangle}
{\frac{\vert {\bf u} \vert^2}{2}}.$ (17)

Then, ${\bf p}$ can be written by ${\bf p}'$ as
$\displaystyle \vert {\bf p} \rangle$ $\textstyle =$ $\displaystyle B\vert {\bf v} \rangle,$  
  $\textstyle =$ $\displaystyle \frac{B\vert {\bf u} \rangle}{\sqrt{2a_r}},$  
  $\textstyle =$ $\displaystyle \frac{\vert {\bf p}' \rangle a_r}{\sqrt{2a_r}},$  
  $\textstyle =$ $\displaystyle \frac{\sqrt{2a_r}}{2}\vert {\bf p}' \rangle.$ (18)

Also, noting that
    $\displaystyle \vert {\bf v} \rangle
=
\frac{1}
{\sqrt{2a_r}}
\vert {\bf u} \rangle,$ (19)

${\bf q}$ can be rewritten by
    $\displaystyle \vert {\bf q} \rangle
=
\alpha
\frac{\sqrt{2a_r}}
{2}
\left(
\ver...
...^*}{4a_r}
\vert {\bf u} \rangle
\langle {\bf u} \vert
{\bf p}' \rangle
\right).$ (20)

Putting Eqs. (19) and (20) into Eq. (16), we have
    $\displaystyle Q^{\dag }BQ
=
B - \vert {\bf u} \rangle \langle {\bf q}' \vert
- \vert {\bf q'} \rangle \langle {\bf u} \vert$ (21)

with ${\bf q'}$ defined by
    $\displaystyle \vert {\bf q}' \rangle
= \frac{\alpha}{2}
\left(
\vert {\bf p}' \...
...^*}{4a_r}
\vert {\bf u} \rangle
\langle {\bf u} \vert {\bf p}' \rangle
\right),$ (22)

where
    $\displaystyle \vert {\bf p}' \rangle
=
\frac{1}{a_r}
B\vert {\bf u} \rangle.$ (23)

The transformation by Eq. (21) can be applied to each column vector step by step in which the place occupied by $s$ in Eq. (2) is shifted one by one. Then, the tridiagonalized matrix $B_{\rm TD}$ is given by
    $\displaystyle B_{\rm TD}
=
Q_{n-1}^{\dag }Q_{n-2}^{\dag }\cdots
Q_3^{\dag }Q_2^{\dag }Q_1^{\dag }
B
Q_{1}Q_{2}Q_{3}\cdots
Q_{n-2}Q_{n-1}.$ (24)

Bibliography

1
A. S. Householder, J. ACM 5, 339 (1958).

up
2007-08-18