4.2 Cholesky分解の並列化

本節では， Schur 方程式の求解を並列計算する方法について説明する． すなわち，Cholesky分解の並列化を行うのであるが， これについては既存の多くの研究が存在する． ここでは，定評ある 並列数値計算ライブラリーであるScaLAPACK[3]の 並列Cholesky分解によって実現することにする． その場合， 係数行列 $\mbox{\boldmath$B$}$はブロック巡回分割によって， 各計算機に割り当てられる． 図3の右図は， 大きさ$9$の係数行列 $\mbox{\boldmath$B$}$を$4$つの計算機で並列計算する場合の， ブロック巡回分割による行列の分割状況を示している．

図 3: 係数行列の分割の方法

ある程度大きなサイズのSchur方程式を解く場合， 次のような結果が期待できる．

	元		新
係数行列 $\mbox{\boldmath$B$}$の計算	$\mathcal{O}(n^3m+n^2m^2)$
Schur方程式の求解	$\mathcal{O}(m^3)$	$\Longrightarrow$	計算機の台数に反比例
$\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}'$の計算	$\mathcal{O}(n^3)$
変数などの保持	$\mathcal{O}(n^2)$
係数行列 $\mbox{\boldmath$B$}$の保持	$\mathcal{O}(m^2)$	$\Longrightarrow$	計算機の台数に反比例