片桐孝洋の並列固有値ソルバのページ
Since 10 January, 1999
工事中
密行列
対称行列(標準固有値問題)
- 並列QR法
- Chinchalkarらは,処理対象の密行列を三重対角行列に変換後,
三重対角行列に対するQR法で全固有値,固有ベクトルを求めた[1].
分散方式は列方向に分散させる方式である,(*,
Cyclic)分割方式を 用いている.
- [参考文献]
- [1] S. Chinchalkar and T.F. Coleman: Computing
Eigenvalues and Eigenvectors of A Dense
Real
Symmetric Marix on the NCUBE 6400, Technical
reportm Cornell University, Theory Center,
91-074 (1991)
- 並列分割統治法 (The Divide-and-Conquer Method)
- 二分法 + 逆反復法
- 相似変換により,密行列を三重対角行列に変換後,二分法で固有値を
求め,それを用いて,逆反復法にて固有ベクトルを収束させ,その後
元の行列の固有ベクトルに変換をするというオーソドックスな方法.
この良く知られている方法を用いて並列化を行なった研究者は
数多いが,問題となる部分は固有ベクトルの直交性を保証するための
直交化処理の並列性にある. この方法を用いて,初めて直交化部分を並列化したのは
Sy-shin Loら[1] であるが,彼らの方法では,残差に関する誤差が
悪くなるという問題が生じる. 一方, James W. Demmel らにより開発された ScaLAPACK[2] では,現在改良が試みられているものの,
処理する行列の性質により,直交精度が保証されないばかりが,
メモリ不足で実行不可能になることがある.
また,直交精度が保証されるが,実行時間が遅くなる可能性がある
ソルバとして, Hendrickson , Jessup , Smithによる固有値ソルバ (HJS Solver) がある[3]. 一方,直交精度を保証した上で,並列実行時間を高速化した(並列性の改良を
施した)ソルバとしては, 片桐 ら によるソルバ[4,5,6]がある.
- [参考文献]
- [1] S. Lo, B. Philippe, and A. Sameh: A Multiprocessor
Algorithm for the Symmetric Eigenvalue
Problem,
SIAM J. Sci. Stat. Comput., Vol. 8, No.
2,
pp. s155 - s165 (1987)
- [2] J. Demmel, and K. Stanley: The Performance
of Finding Eigenvalues and Eigenvectors
of
Dense Symmetric Matrices on Distributed
Memory
Computers, Technical report, University
of
Tennessee -- Knoxville, UT-GS-94-254.
- [3] B. Hendrickson, E. Jessup, and C. Smith:
A Parallel Eigensolver for Dense Symmetric
Matrices, Submitted to SIAM J. Sci. Comput.
- [4] 片桐孝洋,金田康正:並列固有値ソルバーの実現とその性能,
情報処理学会研究報告 97-HPC-69, pp.49--54
(1997)
- [5] 片桐孝洋,金田康正:並列固有値ソルバーの実現とその並列性の改良,
並列処理シンポジウム JSPP'98論文集, pp.223--230
(1998)
- [6] T. Katagiri, A Study on Parallel Implementation
of Large Scale Eigenproblem Solver for
Distributed
Memory Architecture Parallel Machines,
Master
thesis, the university of Tokyo (1998)
- 一方,ダウンロード可能なソースコードとしては
PDSYEVX --- ScaLAPACK のルーチン.
- 二分法 + マルチカラー逆反復法
- 日立製作所の直野健、猪貝光祥、山本有作らによって開発された,
並列版の逆反復法. 固有ベクトルに関する直交処理の並列性を抽出し,それを並列化する。
また適用可能行列サイズは、行列の性質に依存しない.
- [参考文献]
- [1] 直野,猪貝,山本:マルチカラー逆反復法による並列固有ベクトル計算,
日本応用数理学会平成7年度会講演予稿集,pp.18--19
(1995).
- [2] 直野,猪貝,山本:並列固有値ソルバーの開発と性能評価,
並列処理シンポジウム JSPP'96論文集,pp.9--16
(1996).
- 並列 Hessenberg QR 法
- 密非対称行列をHessenberg形に変換し,その後,ダブルシフトQR法で
固有値を求めるという,非対称行列の複素固有値を求める際のオーソドックス
な方法の並列化.単一シフトによる方法では,並列性が少ないということが
Greg Henry と van de Geijn の論文 [1]で初めて指摘された.論文[1] では,シフトを複数行なう
アルゴリズムである,マルチシフトQR法により,改善できることが示され,
Greg Henryは実装して評価を行なった. また,van
de Geijnは,並列性の高い新しいデータ分割方法を発表した[2].
さらに 須田 らによって, このデータ分割方法はさらに改良が加えられた[3].
- [参考文献]
- [1] G. Henry and R. van de Geijn: Parallelizing
the QR algorithm for the unsymmetric algebraic
eigenvalue problem : mythis and reality,
SIAM J. Sci. Comput., Vol. 17, No. 4, pp.870
-- 883 (1996)
- [2] R.A. van de Geijn : Storage schemes for
Parallel Eigenvalue Algorithms, Numerical
Linear Algebra, Digital Signal Processing
and Parallel Algorithms, NATO ASI Series
Vol. F70, Springer-Verlag 1991, 639 --
647.
- [3] 須田礼二,西田晃,小柳義夫:並列 Hessenberg
QR法のための新しい データ分割方式と AP1000+
への効率的実装,並列処理シンポジウム JSPP"97論文集,
pp.377 -- 384 (1997)
疎行列
非対称行列
- Arnordi法
関連リンク
- Ken Stanley's Parallel Symmetric Eigensolver
Page
-
- <最終更新日> 99年 1月 新設
katagiri "at" is.uec.ac.jp