Householder Method for Tridiagonalization: Ver. 1.0
Taisuke Ozaki, RCIS, JAIST
The Householder method [1] is a way of transforming
a Hermitian matrix
to a real symmetric tridiagonalized
matrix
.
Let
be a column vector of
,
and consider that the vector
consists of
the real part
and the imaginary part
as
|
|
![$\displaystyle \vert {\bf b} \rangle = \vert {\bf b}_r \rangle
+ i \vert {\bf b}_i \rangle.$](img6.png) |
(1) |
Also let us introduce a vector
of which real
part has just one non-zero component
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).$](img9.png) |
(2) |
Then, consider a mirror transform
bridging the two vectors
and
by
|
|
![$\displaystyle Q^{\dag } = I - \alpha^{*}\vert {\bf v} \rangle \langle {\bf v} \vert,$](img11.png) |
(3) |
where let us assume that
|
|
![$\displaystyle \vert {\bf s} \rangle = Q^{\dag }\vert {\bf b} \rangle.$](img12.png) |
(4) |
Putting Eq. (3) into Eq. (4), and solving it with respect to
, 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).$](img14.png) |
(5) |
Thus, Eq. (5) allows us to write
as
|
|
![$\displaystyle \vert {\bf v} \rangle =
\beta
\left(
\vert {\bf b} \rangle - \vert {\bf s} \rangle
\right)
= \beta \vert {\bf u} \rangle.$](img15.png) |
(6) |
If
is normalized,
is given by
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)$](img23.png) |
(8) |
with
and
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)$](img26.png) |
(9) |
and
|
|
![$\displaystyle a_i = \langle {\bf b}_i \vert {\bf s} \rangle.$](img27.png) |
(10) |
Then, it is verified that
Thus, the transformation
for the Hermitian matrix
is
a similarity transformation, and given by
By defining
|
|
![$\displaystyle \vert {\bf p} \rangle \equiv B\vert {\bf v} \rangle,$](img37.png) |
(13) |
Eq. (12) becomes
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),$](img40.png) |
(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.$](img41.png) |
(16) |
For the numerical stability, we furthermore modify Eq. (16) as shown below.
Let us introduce a vector
as.
|
|
![$\displaystyle \vert {\bf p}' \rangle
=
\frac{B\vert {\bf u} \rangle}
{\frac{\vert {\bf u} \vert^2}{2}}.$](img43.png) |
(17) |
Then,
can be written by
as
Also, noting that
|
|
![$\displaystyle \vert {\bf v} \rangle
=
\frac{1}
{\sqrt{2a_r}}
\vert {\bf u} \rangle,$](img50.png) |
(19) |
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).$](img52.png) |
(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$](img53.png) |
(21) |
with
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),$](img55.png) |
(22) |
where
|
|
![$\displaystyle \vert {\bf p}' \rangle
=
\frac{1}{a_r}
B\vert {\bf u} \rangle.$](img56.png) |
(23) |
The transformation by Eq. (21) can be applied to each
column vector step by step in which the place occupied by
in Eq. (2) is shifted one by one. Then, the tridiagonalized matrix
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}.$](img58.png) |
(24) |
-
- 1
-
A. S. Householder, J. ACM 5, 339 (1958).
2007-08-18