小柳研究室 助手さんアンケート


回答者:西田晃助手

Q 現在、どのような研究をなさっていらっしゃるのですか?

連続な系を計算機上で効率的に扱うための研究が主テーマです.

例えば, 偏微分方程式を数値的に解くことを考えてみましょう. Poisson 方程式のような楕円型の問題では, 境界条件をもとに方程式を静的に 満たす解を計算しますが, これを差分法で近似すると, 大規模な連立1次 方程式を解くことに帰着されます. この手続きを離散化といいますが, このように定式化された問題に対しては, 性質に応じて様々な反復解法を 考えることができます. 現代の計算機はもともとこのような計算を行うために考案されたものですが, 実際にこれらの計算を効率的に計算機上で処理するためには. 問題の数学的 性質や計算の手続きに関する深い理解が必要となります. このことは, 並列 計算機などのスーパーコンピュータを利用して大規模な科学計算を行う場合 に, より重要な前提となってくることは御理解頂けると思います.

これらは, 民生用の計算機関連技術と区別する意味で, High Performance Computing (HPC) と呼ばれていますが, 当研究室はこの分野において常に国内 外で主導的な役割を果たしてきました. 計算機性能の飛躍的な向上によって, 現在では核管理を含む大規模な問題が数値シミュレーションによって代替され つつあり, 科学技術全般において, HPC と密接に関わりのある研究分野は拡大 しています. その点で, HPC は今後の科学技術発展の鍵を握る非常に重要な 分野であると言えるでしょう.

Q 研究室で行われているプロジェクトについて教えて下さい。

代表的なものの一つとして, 反復線形解法の前処理が挙げられます. これは 非常に大規模な連立一次方程式や (もっと扱いが複雑になりますが) 固有値 問題を高速に解くための方法ですが, 当研究室では今までにいくつもの新 しい解法を発表してきました. 現在, block 線 Jacobi 法前処理や multicoloring などの研究が進んでいますが, 初期の成果で有名なものとして は, multigrid 前処理付共役勾配法 (MGCG) が挙げられると思います.

正定値対称行列の解法として, 共役勾配(CG)法はよく用いられていますが, この CG 法は前処理を行なうことにより, さらに収束を加速することができます. この研究は前処理として multigrid (MG)法を使ったもので, MGCG 法と呼ばれ ています. MG 法は, 複数のグリッドを使って収束を加速させる (誤差の長波長 成分を減衰させるには, ある程度粗い格子を使った方がよい) 解法で, pre-smoothing 過程, coarse grid 修正, post-smoothing 過程で構成されます. CG 法の前処理とするためには, MG 法を表す行列が対称正定値となる必要が ありますが, そのための条件としては, MG 前処理の両 smoothing に対称な 反復解法を使い, グリッド間の変換を表す行列が自己随伴である必要があります. 対称な反復解法には, red-black 対称 Gauss-Seidel (RB-SGS)法, 対称 ADI 法などがあり, MGCG 法では普通 RB-SGS を用いています.

拡散係数に非連続性のある Poisson 方程式を解く場合, 非連続性が強くなる につれて MG 法の平均収束率は極めて悪くなり, ほとんど収束しなくなります. また ICCG 法では, 前処理が MG 前処理に比べて軽いものの, 収束率が MGCG 法に比べ非常に悪いため, 収束までの反復回数が多くなるうえに, 収束率は メッシュサイズに依存するため, 問題の大きさが大きくなるにつれて不利に なります. これに対して MGCG 法ではいずれの問題に関しても平均収束率, 反復回数は一定であることが知られていて, 現在では解析的にもその性質が 解明されています.

MGCG 法の分散メモリ型並列計算機上への実装についてですが, MGCG 法は データ並列性を持っているため, データ分散によりロードバランス, プロ セッサ間通信が決まります. したがって, データ分散や通信オーバーヘッド の除去が必要になりますが, これはブロック分割, 通信と計算のオーバー ラップ等を工夫する必要があります. また, MG 法部分の収束率をよくする ためには, 出来る限り粗いグリッドまで使うほうがよいのですが, 通信の オーバーヘッドやプロセッサ使用率の低下についても注意する必要があります. これらを考慮に入れた AP1000+ 上での並列化の結果, スーパーリニアな スピードアップを達成しています.

MGCG は非対称問題に対しても拡張され, また現在では不規則格子上の問題 や, またそのための離散化手法に対する取り組みも進んでいて, 今後の成果 が期待されるところです.

上記の解法は問題の物理的性質に依存した解法でしたが, 問題の性質に依存 しないものとしては, 不完全コレスキー分解を使った ICCG 法などが, 逐次 解法では広く用いられています. 並列計算のための汎用の前処理について, 現時点では決定的なものはないといってよいのですが, 本研究室では, 既約 優対角な正値対称行列に対する解法として, 線ヤコビ法を変形した, 一次元 ブロック分割によるブロック対角線ヤコビ法を使った高並列な前処理を提案, 実装し, 点ヤコビ前処理に比べて高い性能が得られることを示しました. ち なみにこの解法は昨年度の並列ソフトウェアコンテストに用いられ, Starfire, AP3000 部門で優勝した実績もあります:-)

線形計算のもう一つの重要な柱として, 固有値解析が挙げられます. 今までに 紹介した問題と比べて幾分抽象的ですが, 量子化学などで使われることが多い分野 です. 固有値解法には大まかに分けて二つの系統があり, QR 法のような直接 法と, Lanczos 法などの反復法が問題に応じて用いられています. 比較的小規 模な行列については, 全固有値を求める QR 法を用いることができるのですが, 問題サイズ n に対して O(n^3) の計算量が必要になるため, 扱える問題の規模 に限界があります. このため, 大規模疎行列のためのアルゴリズムとしては, Lanczos/Arnoldi 系 (非対称問題に対しては Arnoldi 法を用います.) の反復 解法を用いるのが一般的です. 反復解法では, 近似解をもとに収束を加速する ことが可能ですが, 当研究室では, 非対称行列での加速解法とその並列化を 中心に研究を進めてきました.

近似解は, 元の問題を小次元空間に射影することで計算できますが (具体的には 小次元の固有値問題を解きます,) この計算には QR 法が使われます. QR 法 の計算量は大きいため, この部分を高速に処理する必要がありますが, ある 程度次元が大きくないと解の精度が低下するため, 精度と計算量のトレードオフ が生じます. この問題は QR 法部分を並列化することで解決できるのですが, 従来この分野には, 理論上の並列性 (O(n)) を実際に達成した実装はありません でした. この研究では, 新しいデータ分割法を採用することにより, 同一の 並列化効率を得るために必要な問題サイズ (オーバーヘッドの指標) を従来の 1/4 に抑えることが可能になっています.

以上, 主な研究テーマを紹介しましたが, もっとプロジェクト色の強いテーマと して, 並列線形計算ライブラリの設計・開発などの仕事もあり, これは今年度 末に完成, 公開される予定です.

Q 所属していらっしゃる研究室ならではの特徴がありましたら、教えて下さい。

テーマを見つけることが研究の最重要ステップである, というのが当研究室 の方針です. 基本的には最初から自分の力で研究を進めることになります. 大変に思われるかも知れませんが, それだけ短期間に実力がつくのも事実ですね.

Q 研究室を目指す学生にひとことお願い致します。

基礎的な知識をしっかりと身に付けておいてください. きちんとした基礎があれば, 将来の研究で不自由することはありません. その上で, 常に知的好奇心と問題意識を持って研究に取り組んでいってもらえれば 幸いです.

Q 情報社会についてひとことお願い致します。

現代の情報社会の原点を形成した理念についても, 時には思いを巡らせたいものですね.

 

〔トップページへ〕 〔「研究室紹介」のindexページへ〕
<vu@is.s.u-tokyo.ac.jp>

Last updated on 29 May, 1999