Householder Tridiagonalization

M.P.
2022-05-11

Introduction

  • Useful matrix manipulations through Householder Reflections

(Photo Source: Townsend)

  • Invented by American Mathematician A.S. Householder in 1958 (Kreyszig).

  • Orthogonal projections generate Householder matrices, \( P \), which zero-out values of \( A \) when multiplied (Orthogonal Matrices: Lecture 8).

Introduction to Householder Tridiagonalization

  • Technique to tridiagonalize a symmetric matrix (Kreyszig).

  • Tridiagonal matrix : nonzero entries on main and adjacent diagonals, efficient for storage (Weisstein).

\[ T=\begin{bmatrix} 5&5&0&0\\4&1&3&0\\0&9&7&10\\0&0&-1&-5 \end{bmatrix} \]

  • \( T \) is similar to \( A \): eigenvalues unchanged and there exist \( S,S^{-1} \) such that \( T = SAS^{-1} \) (Rabinoff & Margalit).

Description of Method

  • From an \( n\times n \) symmetric matrix \( A \), must create \( n-2 \) Householder matrices, \( P \):

\[ \begin{equation}P = I - 2\mathbf{u}\mathbf{u}^T\end{equation} \]

  • \( P \) are symmetric (\( P^T = P \)) and orthogonal ( \( P^T=P^{-1} \))(Lee)

  • Compute matrix product in each of \( j \) steps to update \( A \):

\[ A = P_jAP_j^T \]

  • After \( n-2 \) multiplications, the matrix \( A \) will be tridiagonal (Kreyszig).

Description of Method continued ...

\( P_j = I-2\mathbf{u}_j\mathbf{u}_j^T, 1\leq j\leq n-2 \)

  • \( \mathbf{u}_j \) constructed from corresponding columns of A, \( \mathbf{a}_j \).

  • First \( j \) entries of \( \mathbf{u}_j \) are zero, rest are calculated from formulas (see Kreyszig 20.9):

\[ \begin{array}{l} &u_{j+1} = \sqrt{\frac{1}{2}\left( 1+\frac{|a_{j+1,j}|}{s_j}\right)}\\ &u_i = \displaystyle\frac{a_{i,j} \ \mathrm{sgn} (a_{j+1,j})}{2u_{j+1}s_j}, \ j+2 \leq i\leq n \end{array} \]

\[ s_j = \sqrt{ \sum_{i = j+1}^n(a_{i,j})^2} \]

\[ \mathbf{u} = \begin{bmatrix} 0\\ 0\\ \vdots \\ 0\\ u_{j+1}\\ \vdots\\ u_n \end{bmatrix} \]

Octave Code

Error in system2(cmd, code, stdout = TRUE, stderr = TRUE, env = options$engine.env) : 
  '"C:\Octave\Octave-5.2.0\mingw64\bin\octave-cli.exe"' not found