アルゴリズム¶
このライブラリは, \({\hat H}\) および \(z\) が複素数であるか実数であるかに応じて, 次の4種類の計算をサポートする( \({\hat H}\) は複素数の場合はエルミート行列, 実数の場合は実対称行列).
- \({\hat H}\) も \(z\) も両方複素数の場合 : Shifted Bi-Conjugate Gradient(BiCG)法 [1]
- \({\hat H}\) が実数で \(z\) が複素数の場合 : Shifted Conjugate Orthogonal Conjugate Gradient(COCG)法 [2]
- \({\hat H}\) が複素数で \(z\) が実数の場合 : Shifted Conjugate Gradient(CG)法 (複素ベクトル)
- \({\hat H}\) も \(z\) も両方実数の場合 : Shifted Conjugate Gradient(CG)法 (実ベクトル)
いずれの場合も Seed switching [2] を行う. 左ベクトルが \(N_L\) 個, 右ベクトルが \(N_R\) 個(典型的には1個)あるとする. 以下, 各手法のアルゴリズムを記載する.
Seed switch 付き Shifted BiCG法¶
\(G_{i j}(z_k) = 0 (i=1 \cdots N_L,\; j = 1 \cdots N_R,\; k=1 \cdots N_z)\)
do \(j = 1 \cdots N_R\)
\({\boldsymbol r} = {\boldsymbol \varphi_j}\),
\({\tilde {\boldsymbol r}} =\) 任意, \({\boldsymbol r}^{\rm old} = {\tilde {\boldsymbol r}}^{\rm old} = {\bf 0}\)
\(p_{i k} = 0(i=1 \cdots N_L,\; k=1 \cdots N_z),\; \pi_k=\pi_k^{\rm old} = 1(k=1 \cdots N_z)\)
\(\rho = \infty,\; \alpha = 1,\; z_{\rm seed}=0\)
do iteration
\(\circ\) シード方程式
\(\rho^{\rm old} = \rho,\; \rho = {\tilde {\boldsymbol r}}^* \cdot {\boldsymbol r}\)
\(\beta = \rho / \rho^{\rm old}\)
\({\boldsymbol q} = (z_{\rm seed} {\hat I} - {\hat H}){\boldsymbol r}\)
\(\alpha^{\rm old} = \alpha,\; \alpha = \frac{\rho}{{\tilde {\boldsymbol r}}^*\cdot{\boldsymbol q} - \beta \rho / \alpha }\)
\(\circ\) シフト方程式
do \(k = 1 \cdots N_z\)
\(\pi_k^{\rm new} = [1+\alpha(z_k-z_{\rm seed})]\pi_k - \frac{\alpha \beta}{\alpha^{\rm old}}(\pi_k^{\rm old} - \pi_k)\)
do \(i = 1 \cdots N_L\)
\(p_{i k} = \frac{1}{\pi_k} {\boldsymbol \varphi}_i^* \cdot {\boldsymbol r} + \frac{\pi^{\rm old}_k \pi^{\rm old}_k}{\pi_k \pi_k} \beta p_{i k}\)
\(G_{i j}(z_k) = G_{i j}(z_k) + \frac{\pi_k}{\pi_k^{\rm new}} \alpha p_{i k}\)
\(\pi_k^{\rm old} = \pi_k\), \(\pi_k = \pi_k^{\rm new}\)
end do \(i\)
end do \(k\)
\({\boldsymbol q} = \left( 1 + \frac{\alpha \beta}{\alpha^{\rm old}} \right) {\boldsymbol r} - \alpha {\boldsymbol q} - \frac{\alpha \beta}{\alpha^{\rm old}} {\boldsymbol r}^{\rm old},\; {\boldsymbol r}^{\rm old} = {\boldsymbol r},\; {\boldsymbol r} = {\boldsymbol q}\)
\({\boldsymbol q} = (z_{\rm seed}^* {\hat I} - {\hat H}) {\tilde {\boldsymbol r}},\; {\boldsymbol q} = \left( 1 + \frac{\alpha^* \beta^*}{\alpha^{{\rm old}*}} \right) {\tilde {\boldsymbol r}} - \alpha^* {\boldsymbol q} - \frac{\alpha^* \beta^*}{\alpha^{{\rm old} *}} {\tilde {\boldsymbol r}}^{\rm old},\; {\tilde {\boldsymbol r}}^{\rm old} = {\tilde {\boldsymbol r}},\; {\tilde {\boldsymbol r}} = {\boldsymbol q}\)
\(\circ\) Seed switch
\(|\pi_k|\) が最も小さい \(k\) を探す. \(\rightarrow z_{\rm seed},\; \pi_{\rm seed},\; \pi_{\rm seed}^{\rm old}\)
\({\boldsymbol r} = {\boldsymbol r} / \pi_{\rm seed},\; {\boldsymbol r}^{\rm old} = {\boldsymbol r}^{\rm old} / \pi_{\rm seed}^{\rm old},\; {\tilde {\boldsymbol r}} = {\tilde {\boldsymbol r}} / \pi_{\rm seed}^*,\; {\tilde {\boldsymbol r}}^{\rm old} = {\tilde {\boldsymbol r}}^{\rm old} / \pi_{\rm seed}^{{\rm old}*}\)
\(\alpha = (\pi_{\rm seed}^{\rm old} / \pi_{\rm seed}) \alpha\), \(\rho = \rho / (\pi_{\rm seed}^{\rm old} \pi_{\rm seed}^{\rm old})\)
\(\{\pi_k = \pi_k / \pi_{\rm seed},\; \pi_k^{\rm old} = \pi_k^{\rm old} / \pi_{\rm seed}^{\rm old}\}\)
if( \(|{\boldsymbol r}| <\) Threshold) exit
end do iteration
end do \(j\)
Seed switch 付き Shifted COCG法¶
BiCGのアルゴリズムで, \({\tilde {\boldsymbol r}} = {\boldsymbol r}^*,\; {\tilde {\boldsymbol r}}^{\rm old} = {\boldsymbol r}^{{\rm old}*}\) とすると得られる.
\(G_{i j}(z_k) = 0 (i=1 \cdots N_L,\; j = 1 \cdots N_R,\; k=1 \cdots N_z)\)
do \(j = 1 \cdots N_R\)
\({\boldsymbol r} = {\boldsymbol \varphi_j}\), \({\boldsymbol r}^{\rm old} = {\bf 0}\)
\(p_{i k} = 0(i=1 \cdots N_L,\; k=1 \cdots N_z),\; \pi_k=\pi_k^{\rm old} = 1(k=1 \cdots N_z)\)
\(\rho = \infty,\; \alpha = 1,\; z_{\rm seed}=0\)
do iteration
\(\circ\) シード方程式
\(\rho^{\rm old} = \rho,\; \rho = {\boldsymbol r} \cdot {\boldsymbol r}\)
\(\beta = \rho / \rho^{\rm old}\)
\({\boldsymbol q} = (z_{\rm seed} {\hat I} - {\hat H}){\boldsymbol r}\)
\(\alpha^{\rm old} = \alpha,\; \alpha = \frac{\rho}{{\boldsymbol r}\cdot{\boldsymbol q} - \beta \rho / \alpha }\)
\(\circ\) シフト方程式
do \(k = 1 \cdots N_z\)
\(\pi_k^{\rm new} = [1+\alpha(z_k-z_{\rm seed})]\pi_k - \frac{\alpha \beta}{\alpha^{\rm old}}(\pi_k^{\rm old} - \pi_k)\)
do \(i = 1 \cdots N_L\)
\(p_{i k} = \frac{1}{\pi_k} {\boldsymbol \varphi}_i^* \cdot {\boldsymbol r} + \frac{\pi^{\rm old}_k \pi^{\rm old}_k}{\pi_k \pi_k} \beta p_{i k}\)
\(G_{i j}(z_k) = G_{i j}(z_k) + \frac{\pi_k}{\pi_k^{\rm new}} \alpha p_{i k}\)
\(\pi_k^{\rm old} = \pi_k\), \(\pi_k = \pi_k^{\rm new}\)
end do \(i\)
end do \(k\)
\({\boldsymbol q} = \left( 1 + \frac{\alpha \beta}{\alpha^{\rm old}} \right) {\boldsymbol r} - \alpha {\boldsymbol q} - \frac{\alpha \beta}{\alpha^{\rm old}} {\boldsymbol r}^{\rm old},\; {\boldsymbol r}^{\rm old} = {\boldsymbol r},\; {\boldsymbol r} = {\boldsymbol q}\)
\(\circ\) Seed switch
\(|\pi_k|\) が最も小さい \(k\) を探す. \(\rightarrow z_{\rm seed},\; \pi_{\rm seed},\; \pi_{\rm seed}^{\rm old}\)
\({\boldsymbol r} = {\boldsymbol r} / \pi_{\rm seed},\; {\boldsymbol r}^{\rm old} = {\boldsymbol r}^{\rm old} / \pi_{\rm seed}^{\rm old}\)
\(\alpha = (\pi_{\rm seed}^{\rm old} / \pi_{\rm seed}) \alpha\), \(\rho = \rho / (\pi_{\rm seed}^{\rm old} \pi_{\rm seed}^{\rm old})\)
\(\{\pi_k = \pi_k/\pi_{\rm seed},\; \pi_k^{\rm old} = \pi_k^{\rm old} / \pi_{\rm seed}^{\rm old}\}\)
if( \(|{\boldsymbol r}| <\) Threshold) exit
end do iteration
end do \(j\)
Seed switch 付き Shifted CG法¶
BiCGのアルゴリズムで, \({\tilde {\boldsymbol r}} = {\boldsymbol r},\; {\tilde {\boldsymbol r}}^{\rm old} = {\boldsymbol r}^{\rm old}\) とすると得られる.
\(G_{i j}(z_k) = 0 (i=1 \cdots N_L,\; j = 1 \cdots N_R,\; k=1 \cdots N_z)\)
do \(j = 1 \cdots N_R\)
\({\boldsymbol r} = {\boldsymbol \varphi_j}\), \({\boldsymbol r}^{\rm old} = {\bf 0}\)
\(p_{i k} = 0(i=1 \cdots N_L,\; k=1 \cdots N_z),\; \pi_k=\pi_k^{\rm old} = 1(k=1 \cdots N_z)\)
\(\rho = \infty,\; \alpha = 1,\; z_{\rm seed}=0\)
do iteration
\(\circ\) シード方程式
\(\rho^{\rm old} = \rho,\; \rho = {\boldsymbol r}^* \cdot {\boldsymbol r}\)
\(\beta = \rho / \rho^{\rm old}\)
\({\boldsymbol q} = (z_{\rm seed} {\hat I} - {\hat H}){\boldsymbol r}\)
\(\alpha^{\rm old} = \alpha,\; \alpha = \frac{\rho}{{\boldsymbol r}^* \cdot {\boldsymbol q} - \beta \rho / \alpha }\)
\(\circ\) シフト方程式
do \(k = 1 \cdots N_z\)
\(\pi_k^{\rm new} = [1+\alpha(z_k-z_{\rm seed})]\pi_k - \frac{\alpha \beta}{\alpha^{\rm old}}(\pi_k^{\rm old} - \pi_k)\)
do \(i = 1 \cdots N_L\)
\(p_{i k} = \frac{1}{\pi_k} {\boldsymbol \varphi}_i^* \cdot {\boldsymbol r} + \left(\frac{\pi^{\rm old}_k}{\pi_k } \right)^2 \beta p_{i k}\)
\(G_{i j}(z_k) = G_{i j}(z_k) + \frac{\pi_k}{\pi_k^{\rm new}} \alpha p_{i k}\)
\(\pi_k^{\rm old} = \pi_k\), \(\pi_k = \pi_k^{\rm new}\)
end do \(i\)
end do \(k\)
\({\boldsymbol q} = \left( 1 + \frac{\alpha \beta}{\alpha^{\rm old}} \right) {\boldsymbol r} - \alpha {\boldsymbol q} - \frac{\alpha \beta}{\alpha^{\rm old}} {\boldsymbol r}^{\rm old},\; {\boldsymbol r}^{\rm old} = {\boldsymbol r},\; {\boldsymbol r} = {\boldsymbol q}\)
\(\circ\) Seed switch
\(|\pi_k|\) が最も小さい \(k\) を探す. \(\rightarrow z_{\rm seed},\; \pi_{\rm seed},\; \pi_{\rm seed}^{\rm old}\)
\({\boldsymbol r} = {\boldsymbol r} / \pi_{\rm seed},\; {\boldsymbol r}^{\rm old} = {\boldsymbol r}^{\rm old} / \pi_{\rm seed}^{\rm old}\)
\(\alpha = (\pi_{\rm seed}^{\rm old} / \pi_{\rm seed}) \alpha\), \(\rho = \rho / {\pi_{\rm seed}^{\rm old}}^2\)
\(\{\pi_k = \pi_k/\pi_{\rm seed},\; \pi_k^{\rm old} = \pi_k^{\rm old}/\pi_{\rm seed}^{\rm old}\}\)
if( \(|{\boldsymbol r}| <\) Threshold) exit
end do iteration
end do \(j\)
