学会名: Joint Workshop on Computational Chemistry and Numerical Analysis (CCNA 2005)
開催期日: 2005年12月5日-6日
開催場所: 産業技術総合研究所 秋葉原サイト会議室

1. 学会の概要

本会議は科学技術振興機構 戦略的創造研究推進事業「シミュレーション技術の革新と実用化基盤の構築」長嶋チーム主催で開催された国際会議であり,計算材料化学分野の研究者と応用数理分野の研究者との交流を図ることを目的としている。今回は全部で11件の発表があったが,私は第2日目のみ参加した。話題の中心となったのは大規模固有値問題で,アルゴリズムと応用の両面から様々な発表があり,突っ込んだ議論ができて有益だった。

2. 興味深かった講演

特に興味深かった発表および私の発表について,以下にまとめる。

(1) Structure-Preserving Algorithms for Large Scale Eigenvalue Problems
  Zhaojun Bai(Univ. of California, Davis)


一般化固有値問題 Ax = λBx,2次固有値問題 (λ^2 A + λB + C)x = 0,弱い非線形項を持つ非線形固有値問題 (A - λB + E(λ))x = 0 のそれぞれについて,各問題が持つ構造を保存することにより高速・高精度・高安定性を達成する大規模問題向けの反復アルゴリズムが紹介された。これらはすべて,(Lanczos 法などと同じく)元の固有値問題を部分空間に射影して解くという方法を取っており,(i) 射影する部分空間 Q の決定,(ii) Q の正規直交基底 Q_n の生成,(iii) 固有値問題の Q への射影と射影した問題の求解,(iv) 収束のチェックと必要な場合は Q の拡張,というステップからなっている。この際生じる問題として,(a) 最適な(求める固有ベクトルの成分を豊富に含む)Q をどうやって求めるか,(b) 元の固有値問題の構造を保つような射影をどうやって実現するか,(c) 基底 Q_n を安定かつ効率的に生成するにはどうするか,(d) 部分空間 Q の拡張,更新,精密化,あるいは再設定(リスタート)をどのように行うか,を考える必要がある。これについて,上に挙げた3種類の固有値問題に対し,著者の提案した方法が紹介された。

まず一般固有値問題に対して,Algebraic Substructuring Method [1] が紹介された。この方法は構造解析における固有振動数の計算を主な対象としており,領域を2つの部分領域とそれらの境界部に分割し,各部分領域に対する固有値問題を解く。そして,基底 Q_n として,領域1に対する固有ベクトルを全体に拡張したベクトル(領域1以外の節点では0)の主なもの n_1 本,領域2に対する固有ベクトルを全体に拡張したベクトル(領域2以外の節点では0)の主なもの n_2 本,境界部の各節点に対する単位ベクトル(その節点で1,他の節点で0)を取り,Q_n で張られる空間に元の固有値問題を射影する。すると,捨てた(部分領域の)固有ベクトルの大きさを測る尺度を h とするとき,射影した問題の固有値は O(h^2) の誤差で元の問題の固有値に収束し,射影した問題の固有ベクトルは O(h) の誤差で元の問題の固有ベクトルに収束することが示せる。さらに,本アルゴリズムで必要な演算は,すべて領域分割によって得られる縁付きブロック対角という行列の構造を保つため,効率的に計算が行える。さらに,この射影は再帰的に行うことができ,AMLS(Algebraic Multi-Level Substructuring)というアルゴリズムが構成できる。AMLS 法は,固有値の精度は低くてよいが大量の固有値が必要な場合に有効で,発表で示された例題では,200個以上の固有値が必要な場合に Shift-and Invert Lanczos 法より高速とのことであった。

次に,2次固有値問題に対する解法が紹介された。この場合,λ^2 の係数が単位行列になるように問題を (λ^2 - Dλ - F)x = 0 と変形すると,射影に用いる部分空間は,r_0 = x_0,r_1 = Dr_0, r_j = Dr_{j-1} + Fr_{j-2}(j ≧ 2)で定義される2次の Krylov 部分空間とするのが最も良いことが示せる。この空間に基底を生成して射影する Second Order Arnoldi Method [2][3] が,2次の固有値問題に対する射影法となる。本解法は,2次固有値問題を射影により別の2次固有値問題に変換するため,2次固有値問題という数学的構造を保つことができる。このため,固有値が実軸に対して対称,あるいはすべて負など,元の問題の解が持つ構造を保存することができ,その点で線形化法などに比べて優れていることが示された。

最後に,現在進行中の研究として,弱い非線形項を持つ非線形固有値問題の解法が紹介された。他の問題と同じく,この問題でも,Q を最初にどのように生成するか,また,どのようにして Q を拡張するかが主要な問題となる。その方法の例として,Q の初期値としては非線形項 E(λ) を落とした固有値問題の解,あるいは固有値λをある定数σで置き換えた線形固有値問題 (A - λB + E(σ))x = 0 の解を使う方法,Q の拡張方法としては,残差逆反復法で得られた新しいベクトルを,今までの射影空間 Q に直交化させてできるベクトルを加える方法が提案された。有理型,あるいは平方根型の非線形性を持つ固有値問題に適用したところ,これらの方法は,小さいほうから数個の固有値を精度良く求められることが示された。

参考文献
[1] C. Yang, W. Gao, Z. Bai, X. S. Li, L-Q. Lee, P. Husbands and E. Ng: "An Algebraic Method for Large-Scale Eigenvalue Calculation", SIAM Journal on Scientific Computing, Vol. 27, No. 3, pp. 873-892 (2005).
[2] Z. Bai and Y. Su: "SOAR: A Second Order Arnoldi Method for the Solution of the Quadratic Eigenvalue Problem", SIAM Journal on Matrix Analysis and Applications, Vol. 26, o. 3, pp. 640-659 (2005).
[3] Z. Bai and Y. Su: "Dimension Reduction of Second-Order Dynamical Systems via a Secon-Order Arnoldi Method", SIAM Journal on Scientific Computing, Vol. 26, No. 5, pp. 1692-1709 (2005).

感想: Bai 教授は LAPACK の主要メンバーの一人であり,特に固有値問題に対して多数の重要な研究がある。今回は,構造解析の分野で注目されている AMLS 法をはじめとして,最新の研究内容がわかりやすく説明され,大変勉強になった。特に,非線形固有値問題の解法の部分は,現在類似の問題を扱っているだけに,参考になった。

(2) Large-Scale Orbital Calculation using FMO-MO Method
  Yuichi Inadomi 他5名(産総研)


FMO(Fragment Molecular Orbital)法は,大規模な分子の分子軌道計算において,分子を複数の部分(フラグメント)に分割し,各フラグメントごとに密度行列を求め,これらを合成して全体の密度行列を求める方法である。通常のMO法では扱えない巨大な分子が扱えること,各フラグメントの計算が独立に行えるので高い並列性を持つことなどの利点があるが,一方,個々の分子軌道は求められないという短所がある。FMO-MO法はこれを改良した方法で,(i) まずFMO法を実行し,(ii) その結果得られる電子密度を用いてフォック行列を生成し,(iii) このフォック行列に対する一般固有値問題を解くことにより分子軌道を求める,という3つのステップからなる。これにより,線形の一般固有値問題を1回解くだけで分子軌道を求めることが可能となり,セルフコンシステントな解を求めるために固有値問題を繰り返し解く通常のMO法に比べて有利となる。また,フォック行列は密行列に近くなるという性質があること,得られるエネルギー固有値の精度は通常のMO法とほぼ等しいことなどがわかっている。また,必要な軌道は,HOMOおよびLOMOと呼ばれる最上位の占有軌道および最下位の非占有軌道のみである。

本手法を用いて Lysozyme のフロンティア分子軌道,および水中の Lysozyme の分子軌道を求めた。一般固有値問題の解法としては,櫻井・杉浦の複素モーメントによる方法を用いた。その結果,前者は 6005 個の分子軌道を使って約18分で計算でき,うち一般固有値問題の求解に要した時間は 16CPU で 64 秒であった。また,後者は 20758 個の分子軌道を使って約2日間で計算でき,うち一般固有値問題の求解に要した時間は 128CPU で 112 秒であった。

(3) Performance of BLAS-3 Based Tridiagonalization Algorithms on Modern SMP Machines
  Yusaku Yamamoto(Nagoya University)


キャッシュ向けに最適化された三重対角化手法である Bischof および Wu のアルゴリズムについて,Opteron や Power 5 の SMP(Symmetric Multi-Processor)上での性能評価結果を報告した。Wu のアルゴリズムでは,Opteron(1.8GHz)を用いて 11520 元の対称密行列を三重対角化する場合,帯行列化の部分で 4CPU で最大 11GFLOPS(ピークの76%)の性能が得られた。これは 1CPU に対し,3.5倍の加速に相当する。また,Power 5(1.9GHz)では,7680 元の行列に対し,16CPU で 56GFLOPS(ピークの46%)の性能が得られた。加速率は10倍であった。

質疑応答:
Q1: 本発表では Wu のアルゴリズムの性能パラメータ L,M について,各マシン,各行列サイズに応じた最適値を用いていたが,性能はこれらのパラメータに対してどの程度敏感か?また精度はどうか。
A1: 性能は L,M によって大きく変わり,数倍の変化がある。そのため,各パラメータの値から実行前に性能を予測するモデルの開発を行っている。現在,1CPU の場合はモデルがほぼ完成しており,これを用いて様々なマシン,行列サイズに対して性能パラメータの最適値を事前に求められることを確認している。SMP の場合にも,同様のモデルを作成する予定である。なお,性能パラメータの値による精度の変化はほとんどない。

Q2: Opteron での評価結果で,Dongarra のアルゴリズムは行列サイズが大きくなっても性能は一定値に留まるのに対し,Wu のアルゴリズムでは性能が上がっていくのはなぜか。
A2: Dongarra のアルゴリズムでは通常のハウスホルダー法に比べたオーバーヘッドが小さい反面,計算の半分が level-2 BLAS となるため,性能は主記憶とプロセッサ間のスループットに制約されてしまう。一方,Wu のアルゴリズムでは,帯行列の三重対角化などのオーバーヘッドがあるが,キャッシュを有効利用できるため,主記憶スループットによる制約は小さい。そのため,行列サイズが大きくなるにつれてオーバーヘッドの割合が小さくなり,性能はプロセッサのピーク性能に近づく。


学会出張報告のページに戻る
Topに戻る