4.1 係数行列の計算の並列化

本節では，Schur方程式の係数行列の計算をどのように並列化 するか説明する． 並列計算を実装するに当たり， 計算機間のデータ通信にはMPI[9]を利用する．

Schur方程式の係数行列 $\mbox{\boldmath$B$}$の各要素は(4)式の通り， 行ごとに独立して計算することが可能である． このため，原則として各行を各計算機に割り振ることで並列計算を行う． 各計算機で計算する行の割り当てとして， 上から順番に割り振ることにする． 3.1節で説明した手法を用いる場合， 上の行から下の行に移るにつれ計算量が単調に減少するため， このような方法で良好なロードバランスを保てる[22]． 3.3節で説明した手法を用いる場合は， この割り当てではロードバランスが崩れるときがあり， 一行の計算をさらに並列化するのだが， 詳細は[17]を参照されたい． 図2は， 大きさ$9$の係数行列 $\mbox{\boldmath$B$}$を上から順に $4$つの計算機へ割り当てる場合の，行列の分割状況を示している．

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

数値実験の結果， ある程度大きなサイズのSDP問題を解く場合には， 下記の項目において，かなりよいスケーラビリティが得られた． 理想的には，次のような結果が期待できる．

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