Krylov部分空間法などの線形方程式の解法では、主要な算法間にデータ依存性があり、それらの実行をオーバーラップできないため、大規模並列計算する際に通信時間がボトルネックになる問題がある。この解決のために、必要であれば余分な計算も許すことで全体の計算時間を削減する方法が研究されており、sステップCG法[1]などがある。本発表では、Matrix powers kernel[2]という疎行列のべき乗とベクトルの積を計算する既存のアルゴリズムについて説明をした後、これを適用した実際の数値計算結果を掲示する。

[1] A. T. Chronopoulos, C. W. Gear. Implementation of preconditioned s-step conjugate gradient methods on a multiprocessor system with memory hierarchy. Parallel Computing, Volume 11, Issue 1, pp. 37-53, 1989.
[2] J. Demmel, M. Hoemmen, M. Mohiyuddin, K. Yelick. Avoiding communication in sparse matrix computations. in IEEE International Parallel and Distributed Processing Symposium, Apr. 2008.