片桐孝洋の並列固有値ソルバのページ

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