１.　学会の概要

本会議はブルガリア科学アカデミーの並列処理研究所の主催により2年に1回開かれる国際会議である。今年は黒海沿岸の避暑地Sozopolで5日間に渡って開かれ，ヨーロッパ各国，米国，日本などから100人以上が参加した。私は筑波大学の櫻井鉄也助教授のお誘いで，スペシャルセッション "Distributed Numerical Methods and Algorithms for Scientific Computing" で発表する形で参加した。本会議では有限要素法の安定性や誤差解析など離散化手法に関する理論的な発表，あるいは物理系のシミュレーションなど応用分野での発表が多く，線形計算に関する発表，ハイパフォーマンスコンピューティングに関する発表は必ずしも多くなかった。しかし，O. Axelsson，R. Lehoucq など線形計算の分野で著名な研究者が何人も参加しており，興味深い発表をいくつか聞くことができた。

２.　興味深かった講演

特に興味深かった発表について，以下にまとめる。なお，会議録は Springer Verlag より Lecture Notes in Computer Science の1冊として刊行される予定である。

(1) Algebraic Multilevel Preconditioner based on Matching in Graphs
　　L. Zikatanov (Pennsylvania State University, USA)

代数的マルチグリッド法において，グラフのマッチングを用いて粗視化した行列を求める手法が提案され，その収束性が議論された。本手法は必ずしも最適性を持たないが，元の行列の疎性を保つこと，M行列の性質を受け継ぐことなどの優れた性質を持つ。本手法の収束性は粗い空間へのある射影演算子の安定性に依存しており，この安定性は，射影演算子がグラフの（あるやり方で定義される）勾配演算子と可換であることを用いて評価できる。

(2) Eigenvalue Estimates for Preconditioned Saddle Point Matrices
　　O. Axelsson (Uppsala University, Sweden)

鞍点型の対称行列を係数とする連立一次方程式の求解は，非圧縮性流体の計算，線形弾性問題，制約付き最適化問題，領域分割法など，様々な場面で現れる問題である。このような問題を反復法を用いて解く場合，その固有値の分布が収束性に大きく影響する。本発表では，鞍点型の対称行列の固有値の存在範囲に対し，精度の良い上界・下界を新たに導いた。また，これを用いて，(i) 前処理を行わない場合，(ii) 対称性を保つ前処理を行った場合，(iii) 対称性を崩すが，固有値の実部をすべて非負にする前処理を行った場合，の3つについて，固有値の存在範囲を評価した。その結果，問題によって最適な前処理を選ぶ指針を提供することができた。特に，ある問題に対しては最適な計算量のオーダーを達成できる前処理が存在すること，また，ある問題に対しては対称性を崩しても固有値の実部を非負にする前処理を行ったほうが収束が速いこと，などが示された。

感想： 反復法では一般に反復回数の予測が難しいため，直接法に比べ，実行時間の予測や最適な前処理の選択などの自動チューニングがより困難である。本研究は固有値の存在範囲を精度良く求めることにより反復回数の事前比較をある程度可能にしている点で，自動チューニングへの応用ができそうに感じた。特に，前処理により行列が非対称になっても収束性の事前評価が可能であるという点が興味深かった。

(3) A Hybrid Parallel etho for Large Sparse Eigenvalue Problems on a Grid Computing Environment Using Ninf-G/MPI
　　櫻井鉄也, 小瀧義久（筑波大学）, 梅田宏明, 稲富雄一, 渡辺寿雄, 長嶋雲兵（産総研）

大規模疎行列の一般化固有値問題を解くアルゴリズムの一つとして，櫻井・杉浦により最近提案された複素モーメントを用いる方法がある。このアルゴリズムは，複素平面上の任意の指定された領域内にある固有値を求めることができ，かつ計算量のほとんどを占める複素モーメントの計算が極めて粒度の大きな並列性を持つため，注目されている。本発表では，複数のPCクラスタからなるGＲID環境において本アルゴリズムを並列化する場合において，(i) 入力の行列データをマスターから1台1台のPCにNinf-Gを用いて転送する方式，(ii) マスターから各PCクラスタの1台のPCへのデータ転送をNinf-Gを用いて行い，そのデータをPCクラスタ内でMPIによりブロードキャストする方式，の２つを実装し，性能を比較した。その結果，PCの台数が1000台規模と多くなった場合，方式(i)では転送ネックにより性能が飽和・劣化するが，方式(ii)では性能が順調に伸びることを明らかにした。

感想： 参加者の一人から，「このアルゴリズムは固有値が複素数の場合は有効だと思うが，対称行列のように固有値が実数の場合は従来法のほうが速いはず」とのコメントがあった。しかし，並列粒度が著しく高いことを考えると，プロセッサ数が十分多く，かつそれらの間の通信速度が遅く，かつ求めたい固有値がスペクトルの内部にある場合には，このアルゴリズムは Jacobi-Davidson法，Implicit Restart Lanczos 法，Thick Restart Lanczos 法のような効率的な対称行列用の解法と比べても速い可能性がある。どのような状況下だとこのアルゴリズムが最速となるかを調べるのは，面白い研究課題だと思われる。

(4) Eigenvalue Computation with NetSolve Global Computing System
　　S. Shahzadeh-Fazeli (PRiSM Laboratory, University of Versailles, France), N. Emad and J. Dongarra

本発表では，異なる初期ベクトルから出発するERAM（Explicitly Restarted Arnoldi Method）を独立に走らせ，リスタートを行うタイミングで各ERAMが情報交換を行い，その結果を新しい初期ベクトルに反映するMultiple ERAMの実験結果が示された。Multiple ERAMでは，各ERAMの実行が独立のため，極めて粒度の大きな並列性がある。また，ERAMのうち1つが途中で異常終了しても，他のERAMはその結果を自分の初期ベクトルに反映しなければよいだけ（ただしその分収束は遅くなる）のため，耐故障性も高い。さらに，各ERAMも並列化できるため，たとえばPCクラスタ間とPCクラスタ内のような２つのレベルでの並列化が可能である。本発表では，NetSolveを用いてMultilple ERAMをGRID環境向けに実装し，通常のERAMに比べて収束性を大きく向上できることを示した。

感想： 初期ベクトルが異なる複数のクリロフ部分空間から得られる情報を総合して1本の初期ベクトルに集約し，収束性を向上させるというアイディアは非常に面白く，他にも応用がありそうに思った。しかし，この総合・集約をどのように行うか，その数学的内容を聞けなかったのが残念だった。論文を探すなどして調査したい。

(5) Automatic Tuning Technique Exploring within the Hardware-specific Constrained Parameters
　　今村俊幸（電気通信大学），直野健（日立製作所）

線形計算プログラムのチューニングでは，DOループのループ展開の段数が性能に大きな影響を与える。しかし2重ループの場合，内側・外側のループの展開段数をそれぞれ1から10までのみ考えたとしても，可能な組み合わせは100通りにもなり，全探索により最適な組み合わせを探すのには多大な時間がかかる。そこで本研究では，使用できるレジスタ数を考慮することにより探索領域を制限し，かつ実行時間の近似的な指標としてByte/Flopを用いることにより，最適解の存在する範囲を予め絞る方式を提案した。本方式を対称行列の三重対角化における行列ベクトル積とランク2m更新のループに適用し，SR8000/F1およびVPP5000上で評価を行ったところ，どの場合でも最適なループ展開段数を全探索に比べて大幅に少ない時間で求めることができ，三重対角化ルーチン全体では，SR8000/F1で72%，VPP5000で86.8%と極めて高い性能を達成できた。

感想： 発表では，レジスタ数の制約とByte/Flopという指標の2つにより探索範囲が大幅に小さくなる様子が図示され，本手法の有効性が実感できた。本手法はブロック化アルゴリズムにおけるブロックサイズの最適化にも適用可能だと思われるが，その際，制約条件，および近似的な目的関数には何を取ればよいのだろうか。もし良い量を見つけることができれば，有効な手法になると思われる。

(6) Monte Carlo Valuation of Multidimensional American Options through Grid Computing
　　I. Muni Toke and J. -Y. Girard (Ecole Centrale Paris, France)

3つ以上の資産に依存するアメリカン・オプションの価格をモンテカルロ法により効率的に評価するアルゴリズムとして，Longstaff-Schwartz の方法と Ibanez-Zapatero の方法がある。このうち後者は，まず優良格子点を用いた準モンテカルロ法により最適行使境界を（補間により）求め，次にこの最適行使境界の下で通常のモンテカルロ法により価格を求める方法であり，精度が良いことで知られている。本研究では，6台のPCからなる環境で Globus Toolkit を用いてこのアルゴリズムを並列化し，5.7倍程度とMPIによる並列化に近い加速率が達成できることを示した。

(7) Multilevel Methods for Eigenspace Computations in Structural Dynamics
　　U. Hetmaniuk and R. B. Lehoucq (Sandia National Laboratories, USA)

構造物に対する動的解析を行うには，有限要素法による固有値解析を用いるのが標準的な方法である。大規模な構造解析では変数は100万個を超え，様々な周波数に対する応答を精度良く求めるため，計算すべき固有値・固有ベクトルが数百個以上となることも多い。このような大規模固有値解析を行うには，従来からブロック Lanczos 法がよく使われてきたが，この方法では，スペクトルの内部にある固有値を求めたい場合，逆反復を行うために連立一次方程式を繰り返し解くことが必要となる。一方，最近では再帰的な領域分割に基づく新たな方法として Automated Multi-Level Substructuring（AMLS）法が提案されたが，この方法では，領域断面に対応する行列（Schur Complement）を実際に生成し，分解する必要がある。そのため，この行列が巨大になるような応用では実用的でない。今回提案された Component Mode Synthesis では，大域的な（元の行列に対する）固有ベクトルを求める代わりに，部分構造の固有値解析を行ってその結果を用いて元の構造に対する応答を計算することにより，Schur Complement を生成・分解する処理を不要とした。

感想： Implicitly Restarted Arnoldi Method，AMLS法など，大規模固有値計算の分野で画期的な手法を次々と開発してこの分野をリードしてきた Lehoucq の発表であり，最新の話題が聞けて面白かった。Sandia National Laboratories は超大規模の構造シミュレーションをいくつも手がけ，数値計算に対しても次々と先端的な要求を投げかけてくるだけに，数値計算の研究者にとっては非常に刺激の多い場所なのだろうと感じた。今回の発表の中では，今後，計算すべき固有値・固有ベクトルの組数が増えてくるにつれ，疎行列の固有ベクトルに対しても数値的な直交性の確保が問題となってくるだろうという言葉が興味深かった。なお，AMLS に関しては International Journal on Numerical Methods in Engineering に Arbenz，Hetmaniuk，Tuminaro と共著の論文があり，今回の発表に関連したサーベイ論文として DD16 に Hetmaniuk と共著の本発表と同名（"Multilevel Methods for Eigenspace Computations in Structural Dynamics"）の論文があるとのことなので読んでみたい。

３.　写真

招待講演の行われた建物。インターネット・カフェがあったが，日本語は使えなかった。実は無線LANが使えることを後になって知った。

発表の様子。会場は明るく，スクリーンも小さかったため，見やすさは今一つだった。

学会会場の食堂から見たソゾポルの旧市街。

近隣の町ネセバルにて。ネセバルは紀元前20世紀にさかのぼる古い町で，その文化的建築物と町並みがユネスコの世界遺産に登録されている。 写真はネセバルを代表する遺跡の聖ソフィア教会（5世紀〜6世紀）。

学会ディナーにて。ブルガリアの伝統的ダンス。