A Q R QR分解とは？ → × ◆QR分解 QTQ = I （単位行列） ◆応用例 ◆主な計算方法 n m 今回はこの方法に注目

Presentation on theme: "A Q R QR分解とは？ → × ◆QR分解 QTQ = I （単位行列） ◆応用例 ◆主な計算方法 n m 今回はこの方法に注目"— Presentation transcript:

0 QR分解のブロック化 ２００８年　７月１０日 応用数理工学特論　期末発表 深谷　猛

1 A Q R QR分解とは？ → × ◆QR分解 QTQ = I （単位行列） ◆応用例 ◆主な計算方法 n m 今回はこの方法に注目
（直交行列） （上三角行列） QTQ = I （単位行列） ◆応用例 最小二乗問題 長方行列の特異値分解 三重対角化（二重対角化）のブロックアルゴリズム ◆主な計算方法 グラム・シュミットの直交化 ハウスホルダー変換 今回はこの方法に注目

2 ハウスホルダー変換によるQR分解 ◆ハウスホルダー変換 （直交行列） ◆QR分解への適用 → → → （直交行列の積⇒直交行列） →

3 ハウスホルダーQR分解の問題点 両方ともLevel-2 BLAS Level-3 BLASを使うためにブロック化を行う 行列ベクトル積 ：
行列ベクトル積 ： 行列のランク１更新 ： 両方ともLevel-2 BLAS データの再利用性が低いため，計算機の性能が出ない Level-3 BLASを使うためにブロック化を行う

4 ハウスホルダー変換のブロック化 ◆compact-WY representation Y T YT
計算コスト ： O(ml 2) ◆Level-3 BLASによるハウスホルダー変換の作用 2l 回のLevel-2 BLAS 3回のLevel-3 BLAS

5 ハウスホルダーQR分解のブロック化 ◆Fixed-size Blocking （LAPACKで使用されている手法） Level-2 BLAS
1 2 3 → 1 2 3 l （ⅰ）ブロック内のQR分解 → 1 従来（非ブロック化）のアルゴリズム Level-2 BLAS （ⅱ）compact-WY representationの計算 Level-2 BLAS （ⅲ）compact-WY representationの作用 2 3 → Level-3 BLAS

6 QR分解のブロック化におけるポイント ◆ブロック化による高速化の原理 ◆様々なブロック化方法 両者ともブロック幅に依存
Lv.2 全体の計算量は増加 （compact-WY representationの計算） WY Lv.3 計算量 Level-3 BLASの部分で時間短縮 計算時間 両者ともブロック幅に依存 ◆様々なブロック化方法 Variable-size Blocking Recursive Blocking 複数のブロック化方法の組合せ（ハイブリッド型） 計算環境や問題サイズに合ったブロック化が望ましい

7 高速化率 = 非ブロック化での実行時間 / ブロック化での実行時間
数値実験について ◆実験方法 自作プログラム同士（非ブロック化とブロック化） LAPACKのDGEQR2（非ブロック化）とDGEQRF（ブロック化） それぞれ行列サイズを変えて，QR分解の実行時間を測定 （※自作のブロック化プログラムはブロック幅を変化させて測定） 高速化率 = 非ブロック化での実行時間 / ブロック化での実行時間 ◆実験環境 CPU ：　Opteron（2.0GHz） BLAS ：　AMD ACML

8 Level-2 BLASとLevel-3 BLASの性能比較
DGEMV (Level-2 BLAS) ： n × n 行列と n 次元ベクトルの積 DGEMM (Level-3 BLAS) ： n × n 行列と n × n 行列の積 MFLOPS 6～7倍程度の性能差 n

9 ブロック化による高速化率の評価 ◆自作プログラム ◆LAPACKのルーチン 1000×1000 3.84 0.54 30 7.04
行列サイズ 実行時間（秒） 高速化率 非ブロック化 ブロック化 ブロック幅 1000×1000 3.84 0.54 30 7.04 3000×1000 22.7 2.43 40 9.33 3000×3000 174 13.4 60 12.96 ◆LAPACKのルーチン 行列サイズ 実行時間（秒） 高速化率 非ブロック化 （DGEQR2） ブロック化 （DGEQRF） ブロック幅 1000×1000 3.13 0.51 ー 6.09 3000×1000 13.3 1.99 6.69 3000×3000 89.8 11.7 7.67

10 ブロック幅による実行時間の変化 実行時間（秒） best ブロック幅 行列サイズが小さく，Level-3 BLASの性能がでない
（自作プログラムを使用） （サイズ ： 3000×1000） 行列サイズが小さく，Level-3 BLASの性能がでない best Level-3 BLAS以外の演算量の増加 （ブロック内QR分解 & WY representation計算） ブロック幅

11 行列サイズによる高速化率の変化 高速化率 BLASの性能差と同程度 行列のサイズ（正方行列）

12 まとめ ハウスホルダー変換によるQR分解のブロック化を行った．
compact-WY representationを用いてブロック化を行うことで，Level-3 BLASを使うことが可能になった． 自作プログラムを用いた数値実験の結果，最大で13倍程度の高速化を確認できた． LAPACKのルーチンを用いた数値実験の結果，BLASの性能差と同程度の高速化率が確認できた．

13 (補足)QR分解のアルゴリズム ◆non-blocking

14 (補足)QR分解のアルゴリズム ◆fixed-size blocking