matrix/householder.h マニュアル

(The documentation of matrix/householder.h)
Last Update: 2022/2/2


matrix/householder.hでは行列のHouseholder変換を行う関数が定義されている。
Functions to perform the Householder conversion of a matrix are defined in matrix/householder.h.
Householder変換は行列の特異値分解のために用いられる。 特異値分解ではまず行列に左右から繰り返しHouseholder変換を掛けることによって 上三角2重対角行列に変換する。 その上で、得られた上三角2重対角行列をGivens変換によって対角化する。 得られた対角成分が特異値を表す。
The Householder conversion is used for singularvalue decomposition. In the singularvalue decomposition, the original matrix is first converted to an upper-triangular double-diagonal matrix by repeatedly applying the Householder conversion from left and right. Then the upper-triangular double-diagonal matrix is converted to a diagonal matrix using the Givens conversion. The diagonal components of the resultant diagonal matrix represent the singular values.
以下ではHouseholder変換前の行列を \[\begin{equation} \myvector{G}= \begin{pmatrix} g_{1,1} & \cdots & g_{1,N} \\ \vdots & & \vdots \\ g_{N,1} & \cdots & g_{N,N} \end{pmatrix} \label{eq.G} \end{equation}\] 変換後の行列を \[\begin{equation} \myvector{H}= \begin{pmatrix} h_{1,1} & \cdots & h_{1,N} \\ \vdots & & \vdots \\ h_{N,1} & \cdots & h_{N,N} \end{pmatrix} \label{eq.H} \end{equation}\] と表す。また行列\(\myvector{G}\), \(\myvector{H}\)のサイズを \(N\times M\)とする。
Below, the matrices before and after the Householder conversion are represented by \(\myvector{G}\) (eq. \ref{eq.G}) and \(\myvector{H}\) (eq. \ref{eq.H}\), respectively. The size of these matrices are assumed to be \(N\times M\).
行列\(\myvector{G}\)に対して左から掛けるHouseholder変換は、 第1列〜第\(j-1\)列の第\(i\)行以降が0になっている行列に掛けて 第\(j\)列の第\(i+1\)行以降を0にする変換であり、 以下のように定義される。 \[\begin{equation} h_{k,m}= \begin{cases} g_{k,m} & (k=1,\cdots,i-1; m=1,\cdots,M) \\ g_{k,m}(=0) & (k=i,\cdots,N; m=1,\cdots,j-1) \\ \alpha & (k=i,m=j) \\ \beta_m/\alpha & (k=i; m=j+1,\cdots,M) \\ 0 & (k=i+1,\cdots,N; m=j) \\ g_{k,m}+\frac{g_{k,j}(g_{i,m}-\beta_m/\alpha)}{\alpha-g_{i,j}} & (k=i+1,\cdots,N; m=j+1,\cdots,M) \end{cases} \label{eq.householder_l} \end{equation}\] ここで \[\begin{equation} \alpha=-sign(g_{i,j})\sqrt{\sum_{k=i}^N g_{k,j}^2} \label{eq.householder_l.alpha} \end{equation}\] \[\begin{equation} \beta_m=\sum_{l=i}^N g_{l,j}g_{l,m} \hspace{1em} (m=j+1,\cdots,M) \label{eq.householder_l.beta} \end{equation}\] とおいた。図式的に表すと下表のようになる。
The Householder conversion from the left side, applied to a matrix \(\myvector{G}\) that has a value of zero for the 1st to \(j-1\)th columns of \(i\)th and later lows, is defined by eqs. (\ref{eq.householder_l})-(\ref{eq.householder_l.beta}); this conversion makes the \(i+1\)th and later rows of the \(j\)th column to zero. This conversion is visualized in the table below.
  \([1,j-1]\) \(j\) \([j+1,M]\)
\([1,i-1]\) \(g_{k,m}\)
\(i\) \(g_{k,m}(=0)\) \(\alpha\) \(\beta_m/\alpha\)
\([i+1,N]\) 0 \(g_{k,m}+\frac{g_{k,j}(g_{i,m}-\beta_m/\alpha)}{\alpha-g_{i,j}}\)

行列\(\myvector{G}\)に対して右から掛けるHouseholder変換は、 第1行〜\(i-1\)行の第\(j\)列以降が0になっている行列に掛けて 第\(i\)行の第\(j+1\)列以降を0にする変換であり、 以下のように定義される。 \[\begin{equation} h_{m,k}= \begin{cases} g_{m,k} & (m=1,\cdots,N; k=1,\cdots,j-1) \\ g_{m,k}(=0) & (m=1,\cdots,i-1; k=j,\cdots,M) \\ \alpha & (m=i,k=j) \\ \beta_m/\alpha & (m=i+1,\cdots,N; k=j) \\ 0 & (m=i; k=j+1,\cdots,M) \\ g_{m,k}+\frac{g_{i,k}(g_{m,j}-\beta_m/\alpha)}{\alpha-g_{i,j}} & (m=i+1,\cdots,N; k=j+1,\cdots,M) \end{cases} \label{eq.householder_r} \end{equation}\] ここで \[\begin{equation} \alpha=-sign(g_{i,j})\sqrt{\sum_{k=j}^M g_{i,k}^2} \label{eq.householder_r.alpha} \end{equation}\] \[\begin{equation} \beta_m=\sum_{l=j}^M g_{i,l}g_{m,l} \hspace{1em} (m=i+1,\cdots,N) \label{eq.householder_r.beta} \end{equation}\] とおいた。図式的に表すと下表のようになる。
The Householder conversion from the right side, applied to a matrix \(\myvector{G}\) that has a value of zero for the 1st to \(i-1\)th rows of \(j\)th and later columns, is defined by eqs. (\ref{eq.householder_r})-(\ref{eq.householder_r.beta}); this conversion makes the \(j+1\)th and later columns of the \(i\)th column to zero. This conversion is visualized in the table below.
  \([1,j-1]\) \(j\) \([j+1,M]\)
\([1,i-1]\) \(g_{m,k}\) \(g_{m,k}(=0)\)
\(i\) \(\alpha\) 0
\([i+1,N]\) \(\beta_m/\alpha\) \(g_{m,k}+\frac{g_{i,k}(g_{m,j}-\beta_m/\alpha)}{\alpha-g_{i,j}}\)

これらを繰り返し用いることで 行列を上三角2重対角行列に変換できる。 まず\(i=1\), \(j=1\)として左からHouseholder変換を掛ける。 これにより、第1列の第2行以降がすべて0になる。
A matrix can be converted to an upper-triangular double-diagonal matrix by repeatedly applying these conversions. First, a Householder conversion with \(i=1\) and \(j=1\) is applied from the left side; after this conversion, all components in the 1st column of 2nd to last rows are zero.
  1 2 3 4 \(\cdots\)
1          
2 0        
3 0        
4 0        
\(\vdots\) 0        

次に\(i=1\), \(j=2\)として右からHouseholder変換を掛ける。 これにより、第1行の第3列以降がすべて0になる。
Then a Householder conversion with \(i=1\) and \(j=2\) is applied from the right side; the result is zero values for 3rd to later columns of the 1st row.
  1 2 3 4 \(\cdots\)
1     0 0 0
2 0        
3 0        
4 0        
\(\vdots\) 0        

上で\(j=2\)としたのは 値が既に0になっている第1列の第2行以降を変更しないためである。 もしもここで\(j=1\)とすると第1行第2列は0にできるが、 代わりに第1列の第2行以降がノンゼロになってしまう。 Householder変換単独で対角行列を作れないのはこのような事情による。
In the operation above, \(j=2\) was used to avoid changes in the 2nd and later rows of the 1st column that were already zero. If \(j=1\) was used instead, the 2nd column of the 1st row changes to zero; however, the 2nd and later rows of the 1st column reduces to non-zero. A diagonal matrix cannot be obtained by the Householder conversion alone because of this reason.
次に\(i=2\), \(j=2\)として左からHouseholder変換を掛ける。 変換前の行列が「第1列〜第\(j-1\)列の第\(i\)行以降が0」 という条件を満たしているのでこの変換を行うことができる。 \(i=2\)であるので第1行に変化は無く、以下のようになる。
Next, a Householder conversion with \(i=2\) and \(j=2\) is applied from the left side. Note that this conversion is possible because the matrix before the conversion satisfies the requirement that the 1st to \(j-1\)th columns of the \(i\)th and later rows are zero. This conversion does not change the 1st row because \(i=2\). The result of this conversion is as follows.
  1 2 3 4 \(\cdots\)
1     0 0 0
2 0        
3 0 0      
4 0 0      
\(\vdots\) 0 0      

次に\(i=2\), \(j=3\)として右からHouseholder変換を掛ける。 ここで\(j=2\)とできないのは \(i=1\), \(j=2\)のHouseholder変換の説明で述べたのと同じ理由による。 この変換の結果は以下のようになる。
Then, a Householder conversion with \(i=2\) and \(j=3\) is applied from the right side. The reason for choosing \(j=3\) instead of \(j=2\) is same as that explained previously for the Householder conversion with \(i=1\) and \(j=2\). The result of this conversion is as follows.
  1 2 3 4 \(\cdots\)
1     0 0 0
2 0     0 0
3 0 0      
4 0 0      
\(\vdots\) 0 0      

以下、同様の処理を繰り返すことで上三角2重対角行列が得られる。
Repeating these conversions in the same way yields an upper-triangular double-diagonal matrix.
このヘッダファイル内で定義されている関数を以下に示す。 各関数の詳細は関数名をクリックしてリンク先を参照のこと。
Functions defined in this header file are listed below. For details of individual functions, click the links.
関数名
Function name 		機能・用途
Purpose
householder_l
【マニュアル未作成】
[The documentation has yet to be created] 		行列にHouseholder変換を左から掛ける。
Apply a Householder conversion from the left side to a matrix.
householder_r
【マニュアル未作成】
[The documentation has yet to be created] 		行列にHouseholder変換を右から掛ける。
Apply a Householder conversion from the right side to a matrix.
double_diagonal_householder 行列にHouseholder変換を左右から繰り返し掛けることによって 上三角2重対角行列に変換する。
Convert a matrix to an upper-triangular double-diagonal matrix by repeatedly applying Householder conversions from left and right.