Discovery Sagaサイレントキーワード俯瞰

連立一次方程式 / マルチグリッド法 / 共役勾配法 / 前処理 / 並列化 / ベクトル化 / 負荷分散 / ネットワーク / 共役傾斜法 / 偏微分方程式 / 線形方程式 / 反復解法 / 並列処理 / 領域分割 / 異方性問題 / データ構造 / ベクトル計算機 / 偏微分方程式解法 / 代数的マルチグリッド法 / 格納方法

共役勾配法の前処理としては,並列性が高く,かつ収束加速性の良いものが必要であるが,この二つはしばしば矛盾する.この二つを兼ね備えているものとして,代表者らはマルチグリッド前処理を提唱し,その高い性能を実証してきた.
本研究では,これをさらに非構造格子まで拡張し,任意形状の問題や物理定数に異方性のある問題について研究を進めた.SA-AMG法は,問題行列から性質の似たサイズの小さい行列を生成し利用する効率の良い解法であるが,サイズの小さい行列を生成する際に領域分割境界を考慮して生成することにより異方性のある問題でも,効率よく,かつ高並列に実現できることを示した.
またSA-AMG法の実装技術として,ベクトル化の研究を進めた.SA-AMG法内で大きな計算コストを占めるものとして三つの疎行列の積を求める計算が挙げられる.その疎行列積のベクトル性能を出すためには,代表的な疎行列のデータ構造を組み合わせ,三次元弾性体問題に対してはJDSとCRSの組み合わせた手法が最も高速に処理できることを示した.また大規模疎行列を伴う問題に対する実装技術として,分散疎行列の再分散・リオーダリングライブラリを作成し,評価を行った.このライブラリにより,疎行列問題に対して再分散やリオーダリングの処理を動的に、かつ簡易にできる枠組みを実現した.
その他の並列実装技術の基盤的な研究として,有限サイズのmulti-master divisible load問題についての再分散スケジューリング問題について研究し,いくつかのパラメータを同定することにより,シミュレーションが実システムの振る舞いを正しく再現することを示した.関連する問題として,並列分子動力学のデータ分散の問題についても研究し,ノード間相互接続ネットワークのバンド幅やレーテンシが一様でない場合について,最適な並列分散を与える方法を求めた.これらの基本的な技術が,マルチグリッド法の多様なプラットフォームの上での並列実装にどのように生かせるかは今後の課題である.

線形方程式 / 非構造格子 / CG法 / 前処理 / 並列化 / 領域分割 / マルチグリッド法 / Jacobi法 / 偏微分方程式 / 離散化 / 並列処理 / 共役勾配法 / ICCG法 / Jocobi法 / 多重積分 / 有限要素法 / 領域分割法

本研究では、偏微分方程式を不規則な構造をもった格子で離散化した線形方程式の解法を研究し、併せてその並列計算機上への実装を研究した。
1) Bi-CGSTAB法の前処理
本研究ではマルチグリッド(MG)法を前処理として用いるマルチグリッド前処理付Bi-CGSTAB(MGBi-CGSTAB)法を、不規則な構造の有限要素法によって離散化した移流拡散方程式に適用し,数値実験を行なった.この結果,MGBi-CGSTAB法を用いることにより,問題サイズの拡大による収束性の悪化というMILU前処理の欠点を補うとともに,MG法よりも広範な問題に対して高速に収束することを見い出した。
2) 内点消去型領域分割法
現在のところ構造型格子についてであるが、境界を二重にとることにより、キャパシタンス行列の形が単純になり、対角ブロック前処理を用いることにより、ICCG法より少ない演算量で解を求めることができることを示した。AP1000+上での並列化、とくに1領域の複数puによる並列化を実現。
3) 一般行列のCG法前処理
不規則な構造をもった格子で離散化すると、不規則な構造の疎行列を係数とする方程式が得られるが、これに対する一般的な前処理法を研究した。逐次計算では,問題に依存した性質を利用しない方法の中で最も速い前処理の一つとして,不完全コレスキー分解を使ったPCG法(ICCG法)があり,広く用いられているが,並列計算における汎用の前処理について,逐次計算でのICCG法ほど決定的なものはないといってよい.本研究では,逐次計算では有効ではないが並列性の高い,前処理としての定常的な反復法に注目した.そして,線Jacobi法を変形した定常的な反復法から導かれる行列形式のみを利用する並列性の高い前処理を提案,実装した.さらに,数値実験により,点Jacobi前処理と比較して収束が速いことを示した.

【研究分担者】
須田礼仁	東京大学	大学院・情報理工学系研究科	助教授	(Kakenデータベース)
西田晃	東京大学	大学院・情報理工学系研究科	助手	(Kakenデータベース)

【研究分担者】
西田晃	東京大学	大学院・理学系研究科	助手	(Kakenデータベース)
須田礼仁	名古屋大学	大学院・工学研究科	講師	(Kakenデータベース)