MGCG METHOD: A ROBUST AND HIGHLY PARALLEL ITERATIVE METHOD Osamu Tatebe Abstract A multigrid preconditioned conjugated gradient (MGCG) method, which is an iterative method to solve a large sparse matrix, is proposed. The MGCG method is a conjugate gradient method preconditioned by the multigrid method. First, sufficient conditions for a valid multigrid preconditioner are given. Next, the rate of convergence of the MGCG method is investigated for the Poisson equation with constant diffusion coefficient. Local modes of Fourier analysis are useful to analyze all eigenvalues of the multigrid preconditioned matrix, which give an upper bound of the rate of convergence by Chebyshev polynomials. Consequently, the rate of convergence is quite good and independent of the problem size for the two-dimensional Poisson equation. For strongly discontinuous coefficients, the efficient convergence property and robustness of the MGCG method are shown by numerical eigenvalue analysis. This thesis, moreover, studies the parallel MGCG method and its efficient implementation on distributed memory machines. Though there is a trade-off between parallel efficiency and the rate of convergence, it is shown that the parallel MGCG method has both much better rate of convergence and higher parallel efficiency than other methods by evaluating it on stock multicomputers. MGCG 法: ロバストで高効率な並列解法 建部 修見 概要 大規模疎行列の反復解法であるマルチグリッド前処理付き共役勾配法(MGCG 法) の提案を行う. MGCG 法はマルチグリッド法(MG 法)により前処理を行う共役勾 配法である. まず MG 法が共役勾配法の前処理としての条件を満たすための十 分条件を与える. 次に, 拡散係数が一定のポアソン方程式に対して MG 前処理 後の行列の固有値解析を行い, MGCG 法の収束率の解析を行う. それぞれのグ リッドにおけるフーリエ解析のローカルモードを用いることにより, 前処理後 の行列の全ての固有値を解析的に求めることに成功し, チェビシェフ多項式を 用いて MGCG 法の平均収束率, 漸近収束率の上限を求めた. この結果, 2 次元 のポアソン方程式では MGCG 法の収束率は極めて良く, しかも問題サイズによ らないことが分かった. また非連続な拡散係数を持つポアソン方程式に対して は数値的に固有値解析を行うことにより, MGCG 法はそれらの問題に対しても 良い収束性を持ち, ロバストな解法であることが分かった. さらに MGCG 法の 並列化, 分散メモリ型並列計算機上への効率的な実装の研究を行い, 並列効率 と収束性は互いにトレードオフの関係にあるが, 実機で並列 MGCG 法の評価を 行うことにより, トレードオフの点では他の解法に比べ, 高い並列効率と良い 収束率を合わせ持つ優れた解法となることが分かった.