Shur complement 行列のマルチスレッド化 その１

SDP に対する主双対内点法では、Shur complement 行列の全要素の計算と、この行列の Cholesky 分解という二大ボトルネックがある。特に前者のボトルネックは上手に計算すると隠蔽することができる。ただし、いろいろ工夫しても結局、行列積の計算は必要になるので、BLAS を用いている場合にはプロファイリングをして dgemm が一番上に上がって来たら、とりあえずは成功である。
この Shur complement 行列は全ての要素が独立して計算できるので並列計算に向いているが、計算式の関係から、ある行の全ての要素は一つのプロセス（スレッド）で計算した方が有利である（ただし対称行列なので行と列を反対しても議論は同じ）。SDPARA というソフトウェアでは、この Shur complement 行列の各行の計算を MPI とクラスタ計算機を用いて並列化した。これと同じようなアイデアで今回は pthread を用いて、クラスタ計算機ではなくマルチコア CPU 搭載の 1 マシンで並列化を行ってみた。結果についてはその２で報告する。