マルチグリッド前処理付き共役勾配法の並列化
Parallelization of the Multigrid Preconditioned Conjugate Gradient Method

建部 修見   小柳 義夫
Osamu TATEBE   Yoshio OYANAGI
E-mail: {tatebe,oyanagi}@is.s.u-tokyo.ac.jp

東京大学理学部情報科学科 
Department of Information Science, Faculty of Science, the University of Tokyo


概要

マルチグリッド前処理付き共役勾配法(MGCG法)は, 共役勾配法の前処理として
マルチグリッド前処理を行なう方法であり, マルチグリッド法では収束しにく
いような複雑な問題でも簡単に収束する. 本研究ではそのMGCG法の並列化を考
え, 高並列で収束効率の高いMGCG法を提案する. マルチグリッド法の並列化に
は様々な問題点が存在するが, MGCG法の場合はそれらをうまく解決することが
出来る. 次にそのMGCG法を富士通の並列計算機AP1000上に実装し, 最も収束の
速いMGCG法の考察を行なう. さらに並列計算機で良く使用されているScaled
CG法との比較により評価を行なう.


ABSTRACT

A multigrid preconditioned conjugate gradient method (MGCG method),
which uses the multigrid method as a preconditioner of the PCG
method, converges rapidly even for the problems that the original
multigrid method does not converge effectively. This paper considers
parallelization of the MGCG method and proposes the MGCG method with
high parallelism and high efficiency. There are various problems when
the multigrid method is parallelized, however in the case of the MGCG
method, these problems can be successfully settled. Next implementation
of the MGCG method on the Fujitsu multicomputer AP1000 is performed
and the most efficient MGCG method is studied. Then it is evaluated by
comparing with the Scaled CG method that is often used on the
multicomputers.