通常のKrylov部分空間法は、主要な算法間にデータ依存性があり、それらの実行をオーバーラップできないため、大規模並列計算する際に通信時間がボトルネックになる問題がある。この解決のために、必要であれば余分な計算も許すことで全体の計算時間を削減しようとする研究がなされており、古くはCG法[1]から、近年ではGMRES法[2]、ILU0前処理[3]に関するものなどがある。 本発表では、通信削減が必要となる背景[4]、およびMatrix powers kernel[5]という疎行列のべき乗とベクトルの積を計算するアルゴリズムについて説明をする。

[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] M. Mohiyuddin, M. Hoemmen, J. Demmel , K. Yelick. Minimizing communication in sparse matrix solvers. in Proceedings of the 2009 ACM/IEEE Conference on Supercomputing, Nov. 2009.
[3] L. Grigori, S. Moufawad. Communication avoiding ILU0 preconditioner. INRIA, 2013.
[4] M. Hoemmen. Communication-avoiding Krylov subspace methods. PhD thesis, EECS Department, University of California, Berkeley, 2010.
[5] J. Demmel, M. Hoemmen, M. Mohiyuddin, K. Yelick. Avoiding communication in sparse matrix computations. in IEEE International Parallel and Distributed Processing Symposium, Apr. 2008.