The documentation of “matrix/givens.h”

matrix/givens.h マニュアル

(The documentation of matrix/givens.h)

Last Update: 2022/1/31

matrix/givens.hでは行列のGivens変換を行う関数が定義されている。
Functions to perform the Givens conversion of a matrix are defined in matrix/givens.h.

Givens変換は行列の特異値分解のために用いられる。特異値分解では行列をまずHouseholder変換によって上三角2重対角行列にする。その上で、上三角2重対角行列に対して左右から繰り返しGivens変換を掛けることによって対角化する。得られた対角成分が特異値を表す。
The Givens conversion is used for singularvalue decomposition. In the singularvalue decomposition, the original matrix is first converted to an upper-triangular double-diagonal matrix using a Householder conversion. Then the upper-triangular double-diagonal matrix is converted to a diagonal matrix by repeatedly applying the Givens conversion from left and right. The diagonal components of the resultant diagonal matrix represent the singular values.

左から掛けるGivens変換は

行列の第\(k\)行を\(c\times\)第\(k\)行\(+s\times\)第\((k+1)\)行に
行列の第\((k+1)\)行を\(-s\times\)第\(k\)行\(+c\times\)第\((k+1)\)行に

置き換える変換である(ここで\(k\), \(c\), \(s\)は定数)。すなわち、変換前の行列を \[\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} g_{1,1} & \cdots & g_{1,N} \\ \vdots & & \vdots \\ g_{N,1} & \cdots & g_{N,N} \end{pmatrix} \label{eq.H} \end{equation}\] とすると \[\begin{equation} h_{k,j}=cg_{k,j}+sg_{k+1,j} \hspace{1em} (j=1,\cdots,N) \label{eq.givens_l.row_k} \end{equation}\] \[\begin{equation} h_{k+1,j}=-sg_{k,j}+cg_{k+1,j} \hspace{1em} (j=1,\cdots,N) \label{eq.givens_l.row_k1} \end{equation}\] \[\begin{equation} h_{i,j}=g_{i,j} \hspace{1em} (i=1,\cdots,N; i\neq k, i\neq k+1; j=1,\cdots,N) \label{eq.givens_l.other_rows} \end{equation}\] である。
The Givens conversion from the left side is defined as a conversion to modify the matrix as follows:

the \(k\)th row is replaced by \(c\times\)[\(k\)th row]\(+s\times\)[\((k+1)\)th row], and
the \((i+1)\)th row is replaced by \(-s\times\)[\(k\)th row]\(+c\times\)[\((k+1)\)th row],

where \(k\), \(c\), and \(s\) are constants. This conversion is expressed by eqs. (\ref{eq.givens_l.row_k})-(\ref{eq.givens_l.other_rows}), where \(g_{i,j}\) and \(h_{i,j}\) are matrix components of original and converted matrices (eqs. (\ref{eq.G}) and (\ref{eq.H})), respectively.

右から掛けるGivens変換は

行列の第\(k\)列を\(c\times\)第\(k\)列\(+s\times\)第\((k+1)\)列に
行列の第\((k+1)\)列を\(-s\times\)第\(k\)列\(+c\times\)第\((k+1)\)列に

置き換える変換である。これは \[\begin{equation} h_{i,k}=cg_{i,k}+sg_{i,k+1} \hspace{1em} (i=1,\cdots,N) \label{eq.givens_r.column_k} \end{equation}\] \[\begin{equation} h_{i,k+1}=-sg_{i,k}+cg_{i,k+1} \hspace{1em} (i=1,\cdots,N) \label{eq.givens_r.column_k1} \end{equation}\] \[\begin{equation} h_{i,j}=g_{i,j} \hspace{1em} (i=1,\cdots,N; j=1,\cdots,N; j\neq k, j\neq k+1) \label{eq.givens_r.other_columns} \end{equation}\] と書ける。
The Givens conversion from the right side is defined as a conversion to modify the matrix as follows:

the \(k\)th column is replaced by \(c\times\)[\(k\)th column]\(+s\times\)[\((k+1)\)th column], and
the \((i+1)\)th column is replaced by \(-s\times\)[\(k\)th column]\(+c\times\)[\((k+1)\)th column].

This conversion is expressed by eqs. (\ref{eq.givens_r.column_k})-(\ref{eq.givens_r.other_columns}).

Givens変換を特異値分解のために用いるには \(c\), \(s\)の値を以下のように決定する。左から書けるGivens変換では \[\begin{equation} c=\frac{G_{k,k}}{\sqrt{G_{k,k}^2+G_{k+1,k}^2}} \label{eq.givens_l.c} \end{equation}\] \[\begin{equation} s=\frac{G_{k+1,k}}{\sqrt{G_{k,k}^2+G_{k+1,k}^2}} \label{eq.givens_l.s} \end{equation}\] とする。右から書けるGivens変換ではまず\(\myvector{G}\)を小行列に分割する。 Givens変換の前にHouseholder変換を行うことを前提としているので、 \(\myvector{G}\)は上三角二重対角行列であり、以下のように書ける。 \[\begin{equation} \myvector{G}= \begin{pmatrix} G_{1,1} & G_{1,2} & & \myvector{0} \\ & \ddots & \ddots & \\ & & \ddots & G_{N-1,N} \\ \myvector{0} & & & G_{N,N} \end{pmatrix} \label{eq.G.components.double_diagonal} \end{equation}\] もしもある\(l\)について\(G_{l,l+1}=0\)であれば、 \(\myvector{G}\)は\((1,1)\)成分から\((l,l)\)成分までのブロック小行列と \((l+1,l+1)\)成分から\((N,N)\)成分までのブロック小行列に分割できる。一般にこのような\(l\)は1つとは限らないので、小行列への分割は \[\begin{equation} \myvector{G}= \begin{pmatrix} \myvector{G_1} & & \myvector{0} \\ & \ddots & \\ \myvector{0} & & \myvector{G_M} \end{pmatrix} \label{eq.G.sub_matrices} \end{equation}\] のように書ける。ここで\(M\)は小行列の個数を表し、 \(\myvector{G_1}\), …, \(\myvector{G_M}\)は個々の小行列である。もし全ての\(l\)について\(G_{l,l+1}\neq 0\)であれば\(M=1\)となる。このように小行列に分割した上で、\(G_{k,k}\)が小行列の左上端の成分であれば \[\begin{equation} c=\frac{A_{11}-\sigma}{\sqrt{(A_{11}-\sigma)^2+A_{21}^2}} \label{eq.givens_r.c.edge} \end{equation}\] \[\begin{equation} s=\frac{A_{21}}{\sqrt{(A_{11}-\sigma)^2+A_{21}^2}} \label{eq.givens_r.s.edge} \end{equation}\] とし、それ以外の\(k\)については \[\begin{equation} c=\frac{G_{k-1,k}}{\sqrt{G_{k-1,k}^2+G_{k-1,k+1}^2}} \label{eq.givens_r.c} \end{equation}\] \[\begin{equation} s=\frac{G_{k-1,k+1}}{\sqrt{G_{k-1,k}^2+G_{k-1,k+1}^2}} \label{eq.givens_r.s} \end{equation}\] とする。
The values of \(c\) and \(s\) for the singularvalue decomposition are determined as follows. For Givens conversions from the left side, eqs. (\ref{eq.givens_l.c}) and (\ref{eq.givens_l.s}) are used. For Givens conversions from the right side, the matrix \(\myvector{G}\) is first divided to sub-matrices. As the Householder conversion is assumed to have been applied before the Givens conversion, \(\myvector{G}\) is an upper-triangular double-diagonal matrix written as (\ref{eq.G.components.double_diagonal}). If \(G_{l,l+1}=0\) for \(l\), \(\myvector{G}\) can be divided to block sub-matrices from \((1,1)\) to \((l,l)\) components and from \((l+1,l+1)\) to \((N,N)\) components. As there may be multiple \(l\) that satisfy \(G_{l,l+1}=0\), the division of \(\myvector{G}\) to sub-matrices is written in a general form as (\ref{eq.G.sub_matrices}), where \(M\) is the number of sub-matrices and \(\myvector{G_1}\) to \(\myvector{G_M}\) represent individual sub-matrices; \(M=1\) if \(G_{l,l+1}\neq 0\) for all \(l\). If \(G_{kk}\) is at the upper left corner of a sub-matrix, The values of \(c\) and \(s\) are given by eqs. (\ref{eq.givens_r.c.edge}) and (\ref{eq.givens_r.s.edge}), respectively; otherwise \(c\) and \(s\) are given by eqs. (\ref{eq.givens_r.c}) and (\ref{eq.givens_r.s}), respectively.

(\ref{eq.givens_r.c.edge})(\ref{eq.givens_r.s.edge})式において \[\begin{equation} A_{11}=G_{k,k}^2 \label{eq.A11} \end{equation}\] \[\begin{equation} A_{21}=G_{k,k}G_{k,k+1} \label{eq.A21} \end{equation}\] とする。\(\sigma\)は以下のように決定される。 \(G_{k,k}\)が属する小行列の範囲が \(\myvector{G}\)の\((k,k)\)成分から\((m,m)\)成分まで(\(m\geq k\))であるとする。もし\(m=k\)ならばこの部分は既に対角化が完了しているのでそもそもGivens変換をこれ以上行う必要は無い。そこで\(m>k\)の場合を考える。 \[\begin{equation} M_{11}= \begin{cases} G_{m-1,m-1}^2 & (m=k+1) \\ G_{m-1,m-1}^2+G_{m-2,m-1}^2 & (m\geq k+2) \end{cases} \label{eq.M11} \end{equation}\] \[\begin{equation} M_{12}=G_{m-1,m-1}G_{m-1,m} \label{eq.M12} \end{equation}\] \[\begin{equation} M_{22}=G_{m-1,m}^2+G_{m,m}^2 \label{eq.M22} \end{equation}\] とおく。2次方程式 \[\begin{equation} \sigma^2+\frac{M_{11}+M_{22}}{2}\sigma+M_{11}M_{22}-M_{12}^2=0 \label{eq.sigma} \end{equation}\] を\(\sigma\)について解く。得られた2つの\(\sigma\)のうち、 \(|\sigma-M_{22}|\)が小さくなる方を採択する。
The values of \(A_{11}\) and \(A_{21}\) in eqs. (\ref{eq.givens_r.c.edge}) and (\ref{eq.givens_r.s.edge}) are defined by eqs. (\ref{eq.A11}) and (\ref{eq.A21}), respectively. The value of \(\sigma\) is determined as follows. Let us consider the sub-matrix that \(G_{k,k}\) belongs to. Let this sub-matrix to extend from \((k,k)\) to \((m,m)\) components of \(\myvector{G}\), where \(m\geq k\). If \(m=k\), this part is already a diagonal matrix, meaning that further Givens conversion is not needed. Therefore, consider the cases where \(m>k\). Let \(M_{11}\), \(M_{12}\), and \(M_{22}\) be defined by eqs. (\ref{eq.M11})-(\ref{eq.M22}). Let us solve a quadratic equation (\ref{eq.sigma}) for \(\sigma\). Two candidates of \(\sigma\) are obtained, and the one for which \(|\sigma-M_{22}|\) is smaller is adopted as the final solution.

このヘッダファイル内で定義されている関数を下表に示す。また関数の呼び出し構造を表の下のツリーに示す。特異値分解で直接用いられる関数はdouble_diagonal_2_diagonalであり、その関数からの内部呼び出しの形で他の関数が呼び出される。 Givens変換を左右から掛ける1回1回の操作を行うのは givens_l,givens_rである。各関数の詳細は関数名をクリックしてリンク先を参照のこと。
Functions defined in this header file are listed in the table below. The tree under the table shows the structure of function call. Although many functions are defined in this header file, only the function double_diagonal_2_diagonal is called directly in the singularvalue decomposition; all other functions are called internally within double_diagonal_2_diagonal. Single Givens conversions from left and side are implemented by givens_l and givens_r, respectively. For details of individual functions, click the links.

関数名 Function name	機能・用途 Purpose
givens_l 【マニュアル改訂中につき非公開】 [Documentation is not open as it is under revision]	上三角二重対角行列にGivens変換を左から掛ける。 Apply the Givens conversion from the left side to an upper-triangular double-diagonal matrix.
givens_r 【マニュアル改訂中につき非公開】 [Documentation is not open as it is under revision]	上三角二重対角行列にGigens変換を右から掛ける。 Apply the Givens conversion from the right side to an upper-triangular double-diagonal matrix.
givens_l_getcossin 【マニュアル改訂中につき非公開】 [Documentation is not open as it is under revision]	上三角二重対角行列に左から掛けるGivens変換の\(c\)と\(s\) ((\ref{eq.givens_l.c})(\ref{eq.givens_l.s})式) を計算する。 Compute the values of \(c\) and \(s\) in the Givens conversion to be applied from the left side to an upper-triangular double-diagonal matrix (eqs. \ref{eq.givens_l.c} and \ref{eq.givens_l.s}).
givens_r_getcossin 【マニュアル改訂中につき非公開】 [Documentation is not open as it is under revision]	上三角二重対角行列に右から掛けるGivens変換の\(c\)と\(s\) ((\ref{eq.givens_r.c.edge})-(\ref{eq.givens_r.s})式) を計算する。 Compute the values of \(c\) and \(s\) in the Givens conversion to be applied from the right side to an upper-triangular double-diagonal matrix (eqs. \ref{eq.givens_r.c.edge}-\ref{eq.givens_r.s}).
givens_getsigma 【マニュアル改訂中につき非公開】 [Documentation is not open as it is under revision]	(\ref{eq.givens_r.c.edge})(\ref{eq.givens_r.s.edge}) 式に登場する\(\sigma\)の値を (\ref{eq.sigma})式に基づいて計算する。 Compute the value of \(\sigma\) that appears in eqs. (\ref{eq.givens_r.c.edge}) and (\ref{eq.givens_r.s.edge}) based on eq. (\ref{eq.sigma}).
givens_getGTG 【マニュアル改訂中につき非公開】 [Documentation is not open as it is under revision]	(\ref{eq.givens_r.c.edge})(\ref{eq.givens_r.s.edge}) 式に登場する\(A_{11}\), \(A_{21}\)の値を (\ref{eq.A11})(\ref{eq.A21})式により計算する。 Compute the values of \(A_{11}\) and \(A_{21}\) that appear in eqs. (\ref{eq.givens_r.c.edge}) and (\ref{eq.givens_r.s.edge}) using eqs. (\ref{eq.A11}) and (\ref{eq.A21}).
givens_getlt 【マニュアル未作成】 [The documentation has yet to be created]	変換前の行列\(\myvector{G}\)を構成する小行列の要素範囲を調べる。 Survey the index range of a sub-matrix that constitutes the matrix \(\myvector{G}\) before the conversion.
double_diagonal_2_diagonal 【マニュアル改訂中につき非公開】 [Documentation is not open as it is under revision]	Givens変換を繰り返し適用することによって上三角2重対角行列を対角化する。 Convert an upper-triangular double-diagonal matrix to a diagonal matrix by repeatedly applying the Givens conversion.
singularvalue_sort 【マニュアル未作成】 [The documentation has yet to be created]	対角化が完了した行列の要素を特異値の大きい順に並べ替える。 Sort diagonal components of a matrix, that has been converted to a diagonal matrix, to the descending order of singular values.

関数の呼び出し構造 (Tree of function call):

double_diagonal_2_diagonal
- givens_l
- givens_r
- givens_l_getcossin
- givens_r_getcossin
  - givens_getsigma
  - givens_getGTG
- givens_getlt
singularvalue_sort