三重対角化アルゴリズムの性能評価 早戸拓也・廣田悠輔

はじめに a b T A=AT Aの固有値 Aの固有ベクトル Hi [Hn-2…H1]A[Hn-2…H1]T=T ハウスホルダー変換 A=AT n T Aの固有値 逆変換 三重対角化 Aの固有ベクトル ハウスホルダー変換を使用した相似変換 a = b i Hi [Hn-2…H1]A[Hn-2…H1]T=T はじめに本発表ではA=ATとなるような行列の固有ベクトルを求める計算時間の高速化を目的としています。 その過程で行列Aをハウスホルダー変換によって三重対角化行列Tに変換することが必要となり ます。 この部分のことを三重対角化といいます。 この部分の計算量がかなり多いことから高速化の手法として、どんがらやビショップがのていあんアルゴリズムが提案されています。 ただ、三重対角化を高速化すると，この逆変換の部分が低速になってしまうことがあり，Aの固有ベクトルの計算時間が必ずしも高速化されるといえません。 ハウスホルダー変換はベクトルaをこのようなベクトルbにするような行列Hをもちいて三重対角化行列Tに変換することをいいます。 今回Aの固有ベクトルを求めたいので，Tの固有ベクトルにこのような行列をほどこす逆変換によってAの固有ベクトルをもとめることができます。 逆変換 A[Hn-2…H1]Tui=λi[Hn-2…H1]Tui Tui=λiui

Dongarra 依然としてBLAS2の計算が必要 原理 BLAS3 BLAS2 保存するベクトル数が大切 複数本のピボット行・列を溜めておき，後でまとめて更新 BLAS3 = – × – × BLAS2 保存するベクトル数が大切 依然としてBLAS2の計算が必要

Bischof A 逆変換の演算量が倍増 B T 帯幅の設定が大切 原理 BLAS3 密行列Aを半帯幅LBの帯行列Bに変換 帯行列化 村田法 LB A B T BLAS3 村田法の逆変換 村田法 三重対角化 逆変換 固有値計算 帯行列化の逆変換 逆変換の演算量が倍増

Bischof-帯行列化について 左からH を乗算 右からHT を乗算 左から直行行列H を乗算 ハウスホルダー変換では

Bischof + Dongarra(Wuのアルゴリズム) 原理 帯行列の生成にする際，ブロックピボット行・列を保存しておき， 　 後でまとめて更新 = – × 帯幅と保存するブロック列数が大切

実験に使用する解法のパラメーター A[Hn-2…H1]Tui=λi[Hn-2…H1]Tui 帯行列化の逆変換 LB MB A[Hn-2…H1]Tui=λi[Hn-2…H1]Tui Bui=λiui […HMB2+MB2…HMB2+1HMB2…H1]Tui MB2 解法 LB MB MB2 LAPACK Dongarra † Wu + Bischof 20 40 100 1 2 4 †:ユーザー設定不可

実験環境 計算機環境 テスト行列 アルゴリズム Xeon X5355 2.66 [GHz] (Quad-core × 2) 2コアごとに L2 キャッシュ 4MB Red Hat Enterprise WS release 4 Intel Fortran Compiler 9 Intel Math Kernel Library テスト行列 対称乱数行列 n = 3000，6000 アルゴリズム LAPACK Wu それでは行なった評価実験について説明を行ないます． スライドの8コアXeonを使用して， LAPACK およびWuの三重対角化アルゴリズムを評価を行ないました． テスト問題としてn=3000,6000の対称乱数行列を使用しました． LB, MB, MB2 の説明は必要か

それぞれの最適値となるLB， MB，MB2で評価 PU数が大きい場合にLAPACKより高速 まず，プロセッサ数に対する，固有ベクトルの演算時間はこのようになりました． プロセッサ数に対する高速化率は Wu のアルゴリズムが LACACK よりも高くなり， N = 6000 ではプロセッサ数が大きい場合にWuのアルゴリズムはLAPACKより高速となりました． それぞれの最適値となるLB， MB，MB2で評価 PU数が大きい場合にLAPACKより高速

それぞれの最適値となる LB， MB，MB2 で評価 Wu のアルゴリズムの実行時間の内訳 Wu のアルゴリズムの実行時間の内訳はこのようになりました． いずれの場合でも，村田法の逆変換が5割以上を占めるという結果になりました． 特にプロセッサ数が多い場合，村田法の逆変換の占める割合が高いという結果になっています． それぞれの最適値となる LB， MB，MB2 で評価 村田法の逆変換が大半を占める

各LB(帯幅)での総演算時間 LBを大きく取ると高速 MB = 2，MB2 = 2 で評価 各LBでの総演算時間はこのようになりました．

各MBでのブロック帯行列化の演算時間 LB=100で評価 MBによって演算時間は大きく変化しない PU 数に応じて実行時間が減少 N = 3000, 6000 のいずれの場合でも，MBの変化によって殆ど変化しませんでした． また，いずれのMBの値でも，プロセッサ数の増加によって実行時間は順調に減少しました． MB = 2 LB=100 ではMBによって大きく変化しない．もともと全体に占める割合は10%程度 LB=100で評価 MBによって演算時間は大きく変化しない PU 数に応じて実行時間が減少

各MB2での帯化の逆変換の演算時間 LB=100で評価 PU 数に応じて実行時間が減少 PU 数が大のときMB2が大で高速 LB=100で圧倒的に高速 MB1=2 ブロック帯行列からの逆変換．全体の15%前後をしめていた LB=100で評価 PU 数に応じて実行時間が減少 PU 数が大のときMB2が大で高速

まとめ Wuのアルゴリズムを8コアXeonマシンで評価した． 行列サイズが大きい場合，PU数が多い場合，適切なパラメ ータを設定することによりLAPACKより高速となった． Xeonマシンでは帯幅LBを大きくとると高速となった． MB2に適切な値を設定することにより，ブロック帯行列の逆 変換が高速となった． MBを変化させても殆ど演算時間は変化しなかった． 大半を占める村田法の逆変換が高速化 ブロック帯行列化で保存するベクトル数MB

(補足)演算量について 演算量 ハウスホルダーの演算量: 固有値を求めるための演算量: 逆変換: 行列ベクトル積の演算量: rank-2更新の演算量: 固有値を求めるための演算量: 分割統治法 QR法 逆変換: 約 (4/3)n3 約 (2/3)n3 約 (2/3)n3 O(n2)～ O(n3) 約 2n2 m