近年，大規模な線形問題に対して高性能計算機を用いて高速に解く解法が求められている．そのような大規模な問題に有効な解法として，問題行列から未知数の少ない問題行列を作成し効率良く解く手法が知られている．このような手法をマルチレベルな解法という．未知数の少ない問題は粗いレベルと呼ばれる．このマルチレベルな解法について多くの研究がなされてきた．我々はマルチレベルな解法の一つであるスムーズド・アグリゲーション代数的マルチグリッド(SA-AMG)法を対象とし高性能計算環境に効率よく適用できるような解法を提案，実装することを本研究の目的とする．

　高性能計算環境は計算機クラスタ等，分散メモリ環境として構築されることが多い．また一方で地球シミュレータにみられるようにベクトル計算機も高性能な環境としてあげることができる．そこで本研究ではSA-AMG法の並列アルゴリズムとベクトルアルゴリズムを提案する．並列アルゴリズムでは異方性問題に対する対応についても考察した．

　SA-AMG法では粗いレベルを生成する際に未知数全体を排反な部分集合に分ける．それらはアグリゲートと呼ばれ，粗いレベルの未知数に対応する．アグリゲート生成手法は収束に大きな影響を与える重要な部分となる．並列SA-AMG法では問題行列を点枝接続行列とみなしグラフを生成する．そのグラフの領域分割により並列化する．並列アグリゲート生成手法は，独立アグリゲート生成と共有アグリゲート生成の二つに分類される．独立アグリゲート生成では領域ごとに独立にアグリゲートを作る．この方法では領域境界上にアグリゲートを作成できない．一方，共有アグリゲート生成では，領域境界上のアグリゲートを領域間で共有する．異方性のない問題では独立アグリゲート生成の方が有効であり，異方性のある問題では共有アグリゲートの方が有効であるとされている．しかし，アグリゲートの生成順序もまた収束に大きく影響を与えるが，そのアグリゲート生成順序についてはほとんど研究がされていない．そこで我々は様々なアグリゲートの生成順序を比較し，等方性問題と異方性問題の両方に最も有効なアグリゲート生成手法について考察する．

　細かいレベルは独立アグリゲート生成手法，粗いレベルは共有アグリゲート生成手法を適用する混合アグリゲート生成手法も入れて，6通りアグリゲート生成手法を比較した．その結果，異方性には弱いとされる独立アグリゲート生成手法も，アグリゲートを境界から生成していくこと，最も粗いレベルで並列直接解法を適用することにより異方性問題に対応できることが分かった．また，異方性問題にも等方性問題にも最も有効な手法は，領域内部で1個のアグリゲートの回りからアグリゲートを生成していく共有アグリゲート生成手法であることが分かった．

　次に上記のアグリゲート生成手法に対応する並列SA-AMG法の実装を示す．並列実装において，アグリゲートを任意の未知数集合に対応することと，それの担当プロセッサを任意なものがとれることが実現されている．これらにより任意のアグリゲート生成手法へ拡張が容易にできる．数値実験では最大1562万自由度の3次元ポアソン方程式や1607万自由度の3次元剛体の問題，異方性のある最大819万自由度の問題を解き有効性を示した．

　マルチレベルな解法に対するベクトル化の研究について，不規則構造を有する問題については研究がほとんど行われていない．そこで不規則な構造を持つ問題に対してSA-AMG法のベクトル化アルゴリズムを研究する．SA-AMG法は構築部と解法部の二つに分けることができる．構築部ではマルチレベルのデータ構造を生成し，解法部ではそのデータ構造を利用して反復して問題を解く．解法部は計算時間の大部分を行列ベクトル積に使われる．また構築部の中で最も大きい処理は3つの疎行列の積である．SA-AMG法内のすべての行列ベクトル積をベクトル計算機上で疎行列ベクトル積に適しているデータ構造として知られるJagged Diagonal Storage(JDS)で格納することを提案し評価する．3行列の積についてはCompressed Row Storage(CRS)やCompressed Column Storage(CCS)なども用いて複数の手法を提案し，ベクトル計算機(NEC SX-6i)上で実験し比較を行った．3次元剛体問題に関する数値実験では3行列積はJDSとCRSを用いたものがもっとも高速であった．NEC SX-6i上で解法部は最大2.7Gflopsでて問題行列とベクトルの積のほぼ90%の効率となった．また3行列積はJDSとCRSを用いることによりほぼ1Gflopsで計算できた．

　超大規模な線形問題を高性能計算機によって高速に解く解法を構築することが、近年求められている。そのような大規模な問題に有効な解法として、問題行列から未知数の少ない問題行列を作成し階層的に効率良く解く手法が知られている。このような手法をマルチレベルな解法という。未知数の少ない問題は粗いレベルと呼ばれる。このマルチレベルな解法について多くの研究がなされてきた。藤井氏は、マルチレベルな解法の一つであるスムーズド・アグリゲーション代数的マルチグリッド(SA-AMG)法を対象とし高性能計算環境に効率よく適用できるような解法を提案、実装を目指した。高性能計算環境は計算機クラスタ等、分散メモリ環境として構築されることが多い。また一方で地球シミュレータにみられるようにベクトル計算機も高性能な環境としてあげることができる。そこで本論文の研究において、SA-AMG法の並列アルゴリズムとベクトルアルゴリズムを提案実装し、並列アルゴリズムでは異方性問題についても分析を行っている。

　SA-AMG法では粗いレベルを生成する際に未知数全体を互いに素な部分集合に分ける。それらはアグリゲートと呼ばれ、粗いレベルの未知数に対応する。アグリゲート生成手法は収束に大きな影響を与える重要な部分となる。並列SA-AMG法では問題行列を点枝接続行列とみなしたグラフの領域分割により並列化する。並列アグリゲート生成手法は、領域境界を共有しない・するにより独立アグリゲート生成と共有アグリゲート生成の二つに分類される。異方性のない問題では独立アグリゲート生成の方が有効であり、異方性のある問題では共有アグリゲートの方が有効であるとされていた。しかし、アグリゲートの生成順序も収束に大きく影響を与えるが、そのアグリゲート生成順序についてはあまり研究がされていなかった。本論文では様々なアグリゲートの生成順序を比較し、等方性問題と異方性問題の両方に最も有効なアグリゲート生成手法について考察している。細かいレベルは独立アグリゲート生成、粗いレベルは共有アグリゲート生成を適用する混合アグリゲート生成も含め、6通りアグリゲート生成手法を比較した。その結果、異方性には弱いとされる独立アグリゲート生成も、アグリゲートの境界からの生成、最も粗いレベルでの並列直接解法の適用により異方性問題に対応できることを示した。数値実験によると、異方性問題にも等方性問題にも最も有効な手法は、領域内部で1個のアグリゲートの回りからアグリゲートを生成する共有アグリゲート生成であった。

　上記の種々のアグリゲート生成手法に対応する汎用的な並列SA-AMG法の実装を次に示した。汎用的な点として、並列実装において、アグリゲートを任意の未知数集合に対応することと、それの担当プロセッサを任意なものがとれることが実現されており、任意のアグリゲート生成手法へ拡張が容易にできるソルバとなっている。数値実験では最大1562万自由度の3次元ポアソン方程式や最大1607万自由度の3次元剛体の問題、最大819万自由度の異方性問題を解きソルバとしての有効性を示した。

　マルチレベルな解法に対するベクトル化の研究について、不規則構造を有する問題については研究がほとんど行われておらず、これを解決することを目指して不規則な構造を持つ問題に対してSA-AMG法のベクトル化アルゴリズムを研究している。SA-AMG法は構築部と解法部の二つに分けることができる。構築部ではマルチレベルのデータ構造を生成し、解法部ではそのデータ構造を利用して反復して問題を解く。解法部は計算時間の大部分を行列ベクトル積に使われる。また構築部の中で最も大きい処理は3つの疎行列の積である。

SA-AMG法内のすべての行列ベクトル積をベクトル計算機上で疎行列ベクトル積に適しているデータ構造として知られるJagged Diagonal Storage(JDS)で格納することを提案し評価する。3行列の積についてはCompressed Row Storage(CRS)やCompressed Column Storage(CCS)なども用いて複数の手法を提案し、ベクトル計算機(NEC SX-6i)上で実験し比較を行った。3次元剛体問題に関する数値実験では3行列積はJDSとCRSを用いたものがもっとも高速であることを示した。NEC SX-6i上で解法部は最大2.7Gflopsを達成して問題行列とベクトルの積のほぼ90%の効率となった。また3行列積はJDSとCRSを用いることによりほぼ1Gflopsで計算できることを示した。

　本論文は近年注目されている解法であるSA-AMG法を取り上げ、並列計算環境とベクトル計算環境という代表的な高性能計算環境への適用をした。その中でアグリゲート生成戦略や並列実装、3行列積のベクトル化など様々な知見を得ている。よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。