１.　学会の概要

本学会は，応用数理学会の新しい研究集会の第１回である。今回は，固有値計算法とその応用について全部で12件の発表があり，50人程度の参加者があった。

２.　興味深かった講演

今回聴講した講演のうち，興味深かったものに関するメモを以下にまとめる。なお，研究会のプログラムは http://www.cs.tsukuba.ac.jp/~sakurai/mc.html で見ることができる。

(1) 高速なライブラリには注意 〜性能安定化の必要性〜
　　今村俊幸（電通大）

プログラムを高速化する技法の一つとして，ループ展開がある。たとえばLU分解では，ループ展開を行って複数の行あるいは列を同時に消去することにより，レジスタの再利用性を高め，消去演算の性能を大幅に向上させることができる。しかし，ループ展開はレジスタにロードされるデータのストリームを増やすため，配列サイズによってはキャッシュのカラムコンフリクト等が生じ，性能が大幅に低下する。

本報告では，このような性能不安定性の生じる条件を定量的に示すとともに，不安定性を回避する方法を示した。また，この方法を実際の行列計算ライブラリに適用し，性能が問題の次元数によらずに安定化されることを示した。

感想： 行列計算ライブラリでは，ピーク性能のみに目が行きがちであるが，本報告が扱っているような性能の安定性も非常に重要な性質であると思う。特にグリッド環境では，問題が与えられたときに利用可能な各計算機上での性能予測を行い，もっとも高速に解が得られる計算機に対して求解を依頼するという使い方が考えられるが，性能予測を高精度に行うには，性能が安定化されていることが不可欠な前提条件となる。我々の開発しているライブラリでも，この方法を取り入れて性能安定化を図りたい。

(2) FMO-MO 法による巨大分子に対する分子軌道の計算
　　稲富雄一（産総研）

タンパク質などの巨大な分子に対して分子軌道法を適用する手法として，Fragment MO 法（FMO法）がある。FMO法では，分子をフラグメントと呼ばれる部分に分け，各フラグメントの密度行列とフラグメントペアの密度行列とを計算し，それから全体の密度行列を求めることにより，通常のMO法に比べて計算量を劇的に削減している。しかし，FMO法のままでは，分子全体に対する分子軌道や軌道エネルギーが計算できないという問題点があった。

そこで，分子軌道法を復元するために考えられた方法がFMO-MO法である。この方法では，FMO法で得られた分子全体の密度行列を元にFock行列を計算し，一回だけ一般化固有値問題を解く。これにより，分子全体に対する分子軌道と軌道エネルギーを求める。求めたい軌道はHOMO，LUMO付近の10数〜数十個だけなので，求める固有ベクトルの本数もこれだけで済む。Fock行列はほぼ密行列（ある例では全要素の半分が非ゼロとみなさなくてはならない行列）なので，これは対称密行列の少数個の固有値と対応する固有ベクトルを求める問題となる。10969基底関数の問題に対して Opteron で対角化を行った場合，AMDのライブラリであるACMLを用いて約5400秒の時間が必要であった。

感想： FMO-MO法からの固有値ソルバに対する要求が明確に示され，非常に参考になった。Fock行列を作る部分は並列化を行っているのに対し，固有値ソルバの部分は並列化効率が上がらないので１台で実行しているとのことであるが，これは三重対角化のためのハウスホルダー法が細かい通信を大量に必要とするためだと思われる。また，ハウスホルダー法（のDongarraによる多段化版）は全演算量の半分を level-2 BLAS の行列ベクトル積で行うため，Opteron など最新のプロセッサの能力を十分に引き出せていない可能性も大きいと思われる。

一方，Bischof/Wu による三重対角化アルゴリズムは，通信回数が少なく，かつ全演算量のほとんどを level-3 BLAS で行うことができる。固有ベクトルの逆変換の演算量は（実装方法にもよるが）ハウスホルダー法の２倍かかるが，本問題では計算すべき固有ベクトルの本数は非常に少ないため，その部分の時間は問題にならない。したがって，本問題には Bischof/Wu のアルゴリズムが非常に適するのではないかと考えられる。

(3) 可積分特異値分解 I-SVD アルゴリズムの収束性について
　　岩崎雅史，中村佳正（JST／京大）

I-SVD とは，可積分系の考え方を利用した新しい特異値分解アルゴリズムである。このアルゴリズムでは，Lotka-Voltera 方程式の（奇数番目の）解が t → ∞ である行列の特異値に収束することを利用し，LV方程式の離散化（辻本 & 広田，1994）を用いることにより，特異値の計算を行う。

本報告では，提案したアルゴリズムにおいて解が実際に特異値に収束することの証明が２種類紹介された。このうち一方の証明は，時間方向の差分間隔を不等間隔にした場合にも適用できる。また，収束性を向上させるためのシフトの導入法も示された。数値実験の結果，qd法では絶対値の大きい特異値の相対誤差が悪くなる，大規模問題で収束性が不規則になるなどの問題が生じるのに対し，本手法ではそのような問題が起こらず，安定した精度・収束性が得られることが示された。

感想： 可積分系という通常とは異なるアプローチによる新しい特異値分解アルゴリズムの提案であり，大変興味深かった。また，解法としても，QR法，qd法など従来のアルゴリズムを凌駕する特性が示されており，期待が持てそうに感じた。ただ，私が可積分系についての知識がないため，まだ解法の原理・性質を十分には理解できていない。特に次のような点について知りたい。

　・QR法は行列のQR分解を用いた相似変換，qd法はLR分解を用いた相似変換のように，いずれも行列形式で書いた場合にわかりやすい形となるが，I-SVDもこのように行列のわかりやすい分解と対応付けられるのだろうか。

　・QR法は直交化付き同時逆反復法と解釈できるので，なぜシフトをすると収束性が向上するかが理解しやすい。qd法も無限精度の計算ではLR法と等価であることから，シフトの有効性が理解しやすい。I-SVDでも最小特異値に近いシフトを導入すると収束性が向上するというが，これがなぜかは同様に簡単な形で理解できるのだろうか。

　・QR法では，固有値の相対ギャップがどんなに小さくても直交性の高い特異ベクトルを求めることができるが，I-SVDではどうなのだろうか。Dhillon のアルゴリズムでは，相対ギャップが小さい場合には直交性の問題が完全には解決されていない（Relatively Robust Representation が見つからない場合がある）が，Dhillon のアルゴリズムを改良したI-SVDの特異ベクトル計算法（改良型 twisted 分解）では，この問題は解決されているのだろうか。

今後，I-SVDに関する論文を読むなどして，以上の点について調べてみたい。

(4) 実対称固有値問題に対する分割統治法の拡張
　　桑島豊，重原孝臣（埼玉大学）

実対称三重対角行列に対する分割統治法では，行列を２個の三重対角行列の直和 + rank-1の行列 と分解して小さい行列の固有値問題へと帰着させ，この操作を再帰的に行うことにより問題を解く。本報告では，２個の代わりに k 個の部分問題に分割して解く方法が提案された。この解法では，演算量は従来法の約 3/(2k) で済むという。また，精度については，計算の一部で４倍精度演算を行う必要があるが，これを行えば従来法と同等の精度が得られるという。

感想： 興味深かったが，演算量が 3/(2k) ということは，k を大きくすればするほど演算量を減らせることになり，不思議に思える。実際には k は高々√n（nは行列サイズ）までしか大きくできないとのことであるが，このような制限があるということは，k を小さいと見なして計算から落としている箇所があるはずなので，そこを知りたい。また，従来法と比較して高精度計算が必要な部分があるとのことであるが，これは，k が２より大きい場合，ある行列の null space を求める処理が必要となるので，そこが精度を落としている可能性がある（実際，逆反復法による固有ベクトルの計算でも全く同じ問題があり，これを解決するために twisted 分解などの手法が開発されている）。この点についても，より詳しい解析の結果を知りたい。