「行列・固有値問題の解法とその応用」第1回研究集会

--- 研究会ホームページ ---

日時:平成16年11月26日(金) 午前9時50分〜午後5時40分
場所:電気通信大学IS棟2F 215中会議室
   (東京都調布市調布ヶ丘1-5-1)


プログラム

  1. 9:50 ~ 10:00
    • オープニング
      櫻井鉄也(筑波大学)

  2. 10:00 ~ 10:30
    • 高速なライブラリには注意〜性能安定化の必要性〜
      今村俊幸(電気通信大学)

      概要:ソフトウェアのチューニング技術が進展すると共に それ以上の速度で計算機環境は高速化している。しかしながら、 近代的プロセッサの特徴である階層型メモリは数値計算の核となる ライブラリに対して性能の不安定化を及ぼすことが分かってきている。 この不安定性が顕著に現われる事例とそれを回避する安定化技術に ついてその必要性を報告する。

  3. 10:30 ~ 11:00
    • 対称密行列固有値解法の最近の発展 (I)
      --- Relatively Robust Representation アルゴリズム ---
      山本有作(名古屋大学)

      概要:対称密行列の固有値解法に関しては,ここ数年で大きな進展があった。 その一つに,三重対角行列の固有ベクトル計算法として Dhillon,Parlett らに より開発された Relatively Robust Representation アルゴリズムがある。 本アルゴリズムは,固有値のクラスターがある場合でも再直交化をせずに 全固有ベクトルを O(N^2) の計算量で求められる方法であり,三重対角行列 T をコレスキー分解 LLt の形で保持するという技法をはじめ,逆反復の良い初期 ベクトルを求めるための twisted factorization,固有値を高速・高精度に求める ための dqds アルゴリズムなど,いくつもの新開発の技法が巧みに組み合わ されてできている。本報告では,1997年の Dhillon の博士論文を中心にこれらの 技法について紹介する。時間が許せば,それ以降の進展についても触れたい。

  4. 11:00 ~ 11:30
    • 混合型FEM問題に対するBlock型前処理法の効果についての理論的解析
      鷲尾巧(JST・東京大学),久田俊明 (東京大学)

      概要:超弾性体問題やStokes方程式などの混合有限要素離散化で生じる鞍点型問題 に対するBlock型前処理法の効果を理論的に解析する. 第一にこの種の前処理 を行列分離による古典的反復法に適用した場合の安定性を解析し, 次に GMRES法またはMINRES法の前処理として用いた時の効果について考察する. さらに, 実用的ないくつかの実装法を紹介する.

  5. 11:30 ~ 12:00
    • 有限要素法によるEBE-Arnoldi法を用いた大規模並列固有値解析
      松本純一(産業技術総合研究所)

      概要:有限要素法に特化した超大規模固有値問題用に、Arnoldi法を用いた並列ソルバーを紹介する。Arnoldi法は、非常に大きな行列を、絶対値の大 きい固有値から順にN個を含む N元の行列(上Hessenberg行列)に変換する方法である。有限要素解析での固有値問題は、振動解析・系の安定性 解析がほとんどであり、そのときに必要な情報は、低次の振動モード・系の不安定モードの数〜数十の固有値・固有ベクトルである。Arnoldi法はスペ クトル変換を適用することにより、知りたい部分のN個の固有値をもったN元の行列を作成するので、有限要素法での固有値解析に非常に適した方法である。 Arnoldi法アルゴリズムの並列化を有限要素法の特徴を活かした方法(element by element手法) を用いて行い、計算の高速化、省メモリ化を図る。 解析例として、一億万自由度を超える超大規模並列固有値解析を32〜64プロセッサの中規模PCクラスタを使用した分散メモリ型並列解析手法で行った結 果を示す。

  6. 13:00 ~ 13:30
    • 核融合MHD安定性解析における固有値問題の並列計算
      徳田伸二(日本原子力研究所)

      概要:核融合を実現するプラズマ閉じ込め装置(トカマク)の運転では、プラズマの磁 気流体力学的(MHD)な安定性をモニター(監視ならびに制御)することが不可 欠と予想される。MHD安定性解析は行列の一般固有値問題を解くことに帰着す る。現在、その数値計算に数百秒(パソコン)かかるが、モニターのためには、 それを1秒以下にすることが必要である。我々は、固有値問題の並列処理をスー パーコンピュータ上で行うことによって、その計算時間を1,000倍以上高速にす ることを目指している。講演では、その現状と将来性について報告する。

  7. 13:30 ~ 14:00
    • 計算材料科学に於けるDavidson法とNeumann展開型前処理演算子
      澤村明賢(住友電気工業)

      概要:計算材料科学はSchroedinger方程式を解く、という意味で固有値問題だが、離散 化の方法として擬スペクトラル法が用いられている事から、対角スケーリングを 超えた前処理演算子の研究は余り進んでいない。そこで今回擬スペクトラル法と の相性に配慮したNeumann展開型の前処理演算子を提案すると共に、その従来法 との性能比較を行う。

  8. 14:00 ~ 14:30
    • FMO-MO法による巨大分子に対する分子軌道の計算
      稲富雄一(産業技術総合研究所,JST)

      概要:タンパクなどの巨大な分子に対する分子軌道を求める手法の一つとして、フラ グメント分子軌道法に基づいた分子軌道(FMO-MO)法がある。本講演では、FMO-MO 計算の概要と、その問題点について述べる予定である。

  9. 14:30 ~ 15:00
    • 周波数応答に現れる複素固有値問題と数値解法
      加古孝,東田憲太郎(電気通信大学)

      概要:音声生成において重要な周波数応答曲線は複素周波数平面に 有理関数として解析接続される。その極はある固有値問題の 固有値として特徴づけられる。本講演では、その複素固有値 を近似的に計算する反復解法とその有効性について報告する。

  10. 15:30 ~ 16:00
    • 可積分特異値分解I-SVDアルゴリズムの収束性について
      岩崎雅史,中村佳正(JST・京都大学)

      概要:differential qd (dqd) アルゴリズムは,一般項が具体的に書き下せることから漸近解析が容易で,十分な反復回数のもとで上2重対角行列の特異値に近づくことが示されている.LAPACKでは,高速化のために原点シフトを導入したdqdsアルゴリズムを併用しているが,その場合の収束性に関する議論は完全にはなされていない.一方,我々の開発した可積分特異値分解I-SVDアルゴリズムの収束性は, とある変数の単調増加(減少)性に着目することで理論的に証明することができる.本講演では,I-SVDアルゴリズムに関する収束性について説明し,dqdsアルゴリズムの数値的な危険性についても指摘する.

  11. 16:00 ~ 16:30
    • 両側ハウスホルダ変換に対するWilkinsonの著書AEP中のある"技巧"について
      村上弘(東京都立短期大学)

      概要:Wilkinson の代表的著書AEP中にある、エルミート行列の両側ハウスホルダー変換 による三重対角化での記憶階層間の転送を半減される技巧[1]は、文章で記述されており、 その後長らく忘れられているように思われる。それらを具体的に算法として記述し、プロ グラム化し、実際の効果を確かめてみた。さらに非対称行列についても拡張し、扱った。
      Ref: [1] J.H. Wilkinson: "Householder's Process on a Computer with a Two-Level Store", chap.5,sec.32,'Algegraic Eigenvalue Problem',Oxford Univ.Press, 1965.

  12. 6:30 ~ 17:00
    • 実対称固有値問題に対する分割統治法の拡張
      桑島豊,重原孝臣(埼玉大学)

      概要:n 次実対称三重対角行列の固有値問題解法で、現在演算量最小である 従来の 2 分割の分割統治法を拡張した、k 分割の分割統治法を提案する。 提案法は中核をなす、対角行列と階数 k-1 の摂動との和の固有値問題が O(n^2) の演算量で解ければ、従来法の約 3/(2k) の演算量となる。 対角行列と階数 k-1 の摂動との和の固有値問題に対して、 適切な箇所に 4 倍精度演算を用いることで、固有ベクトルの直交性を 保証することを試み、その現状を報告する。

  13. 17:00 ~ 17:30
    • 浮動小数点分布の偏りを利用した近接固有値の計算法
      山本野人,今村俊幸(電気通信大学)

      概要:浮動小数点数の分布は一様ではなく、その密度は0近傍で大きくなる。 このことを利用して、スツルム2分法を用いて近接固有値の分離を行なう。 通常の倍精度計算では分離できない状況であっても、平行移動によって 固有値を0近傍に引き戻せば分離できる可能性がある。 固有ベクトルの計算に関しては、逆反復法を適用する。逆行列を近接固有値間の 距離について展開し、反復の際に足し込みによる情報落ちが起こらないように 注意を払うことで一次独立な固有ベクトルを得ることができる。 講演ではこれらの方法について数値例を挙げて考察する。

  14. 17:30 ~ 17:40
    • クロージング
      片桐孝洋(電気通信大学)

    18:00 ~
      懇親会