ISC 2015 - HPLを補うベンチマーク「HPCG」(前編)

この例では7つの隣接格子点を使う計算であるが、本当のHPCGではもう少し複雑で、次の図に示すように、3×3×3の27要素の現在の値から中心の点の次の値を決めるという問題に対応して、各行の非ゼロ要素の数は27となっている。

行列Aのamn要素の値が、格子点mが格子点nに与える影響の大きさを表すとすると、隣接した格子点ペアに対応するamnはゼロでない値を持つが、大部分のamnはゼロとなる。例えば、i、j、kが100まであるとすると格子点の数は100×100×100で100万となる。そしてmとnは100万まであり、行列Aは100万×100万=1兆要素の行列となる。

しかし、HPCGのように1行に非ゼロ要素は27個しかないと、Aの大部分の要素はゼロで、非ゼロの要素はごく僅かという疎行列になる。

HPLは大多数の要素が非ゼロという密行列の問題であるので、LU分解という方法で、順次、変形を行いながら問題を解いていくが、巨大な疎行列のHPCGの場合は、LU分解でも解けるのであるが効率が悪い。このため、HPCGでは、解xの初期近似値x(0)を作り、Ax(0)を計算してbとの誤差を計算し、それを小さくするよう補正してx(1)