研究集会 「超大規模行列の数理的諸問題とその高速解法」 2007 年 3 月 7 日 完全パイプライン化シフト QR 法による 実対称三重対角行列の 固有値並列計算 宮田 考史　　山本 有作　　張 紹良 　 名古屋大学　大学院工学研究科　計算理工学専攻

目次 はじめに 固有値問題の数値解法 QR 法の並列化 性能差理論解析 数値実験 まとめ シングルシフト QR 法 マルチシフト法 遅延シフト法 提案法 性能差理論解析 数値実験 まとめ

はじめに 本研究で扱う問題 標準固有値問題 計算機を用いた固有値計算 - 行列を扱いやすい形に相似変換 - 固有値は不変 三重対角化 対角化 　本研究で扱う問題 標準固有値問題 　計算機を用いた固有値計算 - 行列を扱いやすい形に相似変換 - 固有値は不変 三重対角化 対角化 実対称行列 三重対角行列 対角行列 対角成分に固有値

シングルシフト QR 法 シングルシフト QR 法 (2)　シフトの更新 ・・・ 相似変換 固有値 非対角成分

シフトの更新 収束を速めるには？ 更新された新しいシフトを用いる Wilkinson シフト 右下 2 × 2 の小行列の固有値 シフト = 右下対角成分に近い値 ・・・ シフト シフト シフト = 固有値 固有値の近似度増加 収束を速めるには？ 更新された新しいシフトを用いる

QR 法の並列化 　マルチシフト法 　遅延シフト法 　提案法

QR 法の並列化 シングルシフト QR 法の演算順序 マルチシフト法（並列化可能） 左上から右下まで 逐次的に実行 （並列化困難） 複数のシフト マルチシフト法（並列化可能） プロセッサ 2 例： 2 シフト プロセッサ 1 m m 右下 m × m 小行列の固有値 → m 個のシフト シフト 1 ： 計算開始 シフト 2 ： 計算開始

マルチシフト法の問題点 （プロセッサの待ち時間） 計算過程 PU 1 PU 2 Time 待ち時間 ① ② ③ ④ △ CPU 使用効率 （並列化不向き） 同期箇所 ① ② ③ ④

並列処理の効率化 マルチシフト法 （Z.BAI and J.DEMMEL 1989） 待ち時間 PU 1 PU 2 △ CPU 使用効率 （並列化不向き） Time ( Step i-1 ) ( Step i ) 古いシフト 遅延シフト法 （R. A. Van De Geijn 1993） PU 1 PU 2 ・・・・ ・・・・ ○ CPU 使用効率 △ 収束性低下 ・・・・ Time ( Step i-2 ) ( Step i-1 ) ( Step i )

収束性の改善 遅延シフト法 （R. A. Van De Geijn 1993） 提案法 克服 PU 1 PU 2 ・・・・ ・・・・ ○ CPU 使用効率 △ 収束性低下 ・・・・ Time ( Step i-2 ) ( Step i-1 ) ( Step i ) シフト更新回数増大 （新しいシフト） 提案法 PU 1 PU 2 ・・・・ ( Step i-1 ) ・・・・ ( Step i ) ○ CPU 使用効率 ○（？） 収束性改善 ・・・・ Time ( Step i-2 ) 克服 △ シフト計算量増大

性能差理論解析

解析準備 実行時間のモデル化 マルチシフト法 遅延シフト法，提案法 行列サイズ，シフト数（= プロセッサ数） 計算機環境固有のパラメータ 平均反復回数（実測値） マルチシフト法 遅延シフト法，提案法 予備的な実験　 　相対誤差 = |予測時間 – 実測時間| / （実測時間）×100 4 種類の計算機環境，8 種類の問題で比較 モデル時間は実測時間とほぼ一致（相対誤差 10 % 程度）

性能差 = （従来法の実行時間） / （提案法の実行時間） 解析結果 性能差 = （従来法の実行時間） / （提案法の実行時間） マルチシフト法と比較 プロセッサ数増加に伴い，性能差増大 （提案法はより高速に成り得る） 遅延シフト法と比較 性能差は収束性にのみ依存 （計算機環境に依存しない） 名古屋大学 情報連携基盤センター （n = 200000） 性能差 プロセッサ数

数値実験

数値実験 評価項目 - 実験環境 - 名古屋大学情報連携基盤センター - C 言語 + OpenMP（共有メモリ型並列計算機に実装） 　評価項目 - 　実験環境 - 名古屋大学情報連携基盤センター 並列計算機　Fujitsu PRIMEPOWER HPC2500 （SPARC64V 2.0GHz ，Memory 512 GB） - C 言語 + OpenMP（共有メモリ型並列計算機に実装） - 収束判定条件 三重対角行列 マシンイプシロン

テスト問題 従来法と同程度 提案法が優勢 性能差 1 = （マルチシフト法の実行時間） / （提案法の実行時間） 性能差 2 = （遅延シフト法の実行時間） / （提案法の実行時間） 提案法が優勢 従来法と同程度

実験結果 ( RANDOM ) 従来法と同程度 1.05 倍 1 割減 提案法について 高速化率 ： 遅延シフト法と同程度 反復回数 ： 遅延シフト法と同程度 マルチシフト法 遅延シフト法 提案法

実験結果 ( PARSEC/CO ) 従来法と同程度 1.04 倍 1 割減 提案法について 高速化率 ： 遅延シフト法と同程度 反復回数 ： 遅延シフト法と同程度 マルチシフト法 遅延シフト法 提案法

実験結果 ( SINH-UPPER ) 提案法が優勢 1.24 倍 2 割減 提案法について 高速化率 ： 遅延シフト法の 1.2 倍 反復回数 ： 遅延シフト法の 2 割減 マルチシフト法 遅延シフト法 提案法

実験結果 ( TRIDIAG(-1,2,-1) ) 提案法が優勢 1.66 倍 3 割減 提案法について 高速化率 ： 遅延シフト法の 1.7 倍 反復回数 ： 遅延シフト法の 3 割減 マルチシフト法 遅延シフト法 提案法

まとめ 本研究では QR 法の並列化を行った． 従来法に対して 　従来法に対して マルチシフト法に比べて，多くのプロセッサを用いるほど，提案法はより高速となった．（並列処理の効率化） 遅延シフト法に比べて，提案法は良い収束性を示した． そのため，遅延シフト法の性能を上回った． 提案法は並列計算機向けの 有力な固有値解法となる可能性がある． 今後の課題 　収束性の理論解析 　分散型への実装