Presentation is loading. Please wait.

Presentation is loading. Please wait.

AllReduce アルゴリズムによる QR 分解の精度について

Similar presentations


Presentation on theme: "AllReduce アルゴリズムによる QR 分解の精度について"— Presentation transcript:

1 AllReduce アルゴリズムによる QR 分解の精度について
山本有作 森大介 張紹良 名古屋大学 大学院工学研究科 計算理工学専攻 張研究室 行列・固有値の解法とその応用 第6回研究会 2008/11/26

2 目次 QR分解 QR分解の並列化アルゴリズム 精度に関する数値実験 理論的誤差解析 まとめと今後の課題 従来のハウスホルダー変換
AllReduceアルゴリズム 精度に関する数値実験 理論的誤差解析 まとめと今後の課題

3 Q A = R QR分解 応用例 行列 A ∈Rm×n を Q ∈Rm×n と R ∈Rn×n に分解する 最小二乗問題 特異値分解の前処理
二重対角化・三重対角化のブロック化アルゴリズム 電子状態計算 m≫n 大規模問題に対する高速かつ高精度な手法が必要

4 QR分解 グラムシュミットの直交化法 ハウスホルダーQR分解 並列化に向く(古典的グラムシュミット法)
計算が逐次的 得られるQ の直交性が良い

5 A A A = QR (従来の)ハウスホルダー変換 QT R あるベクトル x を任意のベクトル y に変換する H1 作用 H2 H x
A H1 作用 H2 作用 H1 作成 H2 作成 H x y (I: 単位行列) → u を正規化 A R QT ・・・ 各ステップの計算は逐次的なため 並列化(高速化)が困難 A = QR ・・・

6 並列化時に考えるべき点 tcomm ≪ tsetup 通信回数の少ないアルゴリズムが必要 以下,分散メモリ型の並列計算機を考える
プロセッサ間の通信量 通信量が大きいと(計算以外の)コストが増加 通信回数 通信回数が多くても(計算以外の)コストが増加 (通信にかかる全時間) = (データ通信時間)+(立ち上げ時間) tcomm tsetup 通信回数の少ないアルゴリズムが必要 以下,分散メモリ型の並列計算機を考える

7 A 合計 2N 回 ハウスホルダー変換の並列化 (2並列) 行列を上下に二分割して 各プロセッサにデータを持たせる。 各ステップ 2回 n
行列を上下に二分割して 各プロセッサにデータを持たせる。 A H (I: 単位行列) → u を正規化 m I. u の生成(||x||2 の計算) 各ステップ 2回 communication II. H = I - 2uuT の作用 update 合計 2N 回 communication

8 AllReduceアルゴリズム*(Langou 2007)
: それぞれ独立に計算可能 A A1 Q1 R1 R1 R2 QR分解はすべて ハウスホルダー変換で行う m/2×n の行列 2回 2n×n の行列 1回 m R A2 Q2 R2 communication m≫n 合計 1 回 A Q1 Q1 O Q このアルゴリズムは再帰的に利用可能 再帰段数が増えるにつれ,計算量は従来のハウスホルダー変換に比べて増加 R R O Q2 Q2 * TSQR(Tall and Skinny QR)アルゴリズムとも呼ばれる

9 比較 手法 従来の ハウスホルダー変換 AllReduce アルゴリズム 計算量 逐次計算 並列計算 通信回数 2N 1 通信量

10 計算量と計算時間(逐次計算) 計算量 k は再帰の段数 ハウスホルダー変換 CPU: Xeon 2.80GHz メモリ: 4GB
行列サイズ: 4000×100

11 本研究の目的 並列性能についてはすでに多くの検証がなされている (Demmel et al. 2008,村上 2008)
精度についてはまだ詳細な報告がない AllReduce アルゴリズムの精度を実験的・理論的に評価する 演算量の増加が精度にどのような影響を及ぼすか?

12 数値実験概要 精度の指標 実験項目 計算機環境 直交性 || QTQ - I ||F 残差 || A - QR ||F
従来のハウスホルダー変換と 2分割のAllReduceアルゴリズムの精度比較 行列サイズ(m, n)依存性 AllReduceの再帰段数を変えたときの精度比較 計算機環境 CPU Xeon 2.80GHz メモリ 4GB コンパイラ GNU C/C++ Compiler

13 数値実験1 乱数行列 A ∈Rm×n を Q ∈Rm×n と R∈Rn×n へ分解 従来のハウスホルダー変換 AllReduceアルゴリズム 再帰の段数は1で固定(2分割) 行列サイズ m n I 4000 100~500 II 1000~5000 100 ||A||_F 最大:1290ぐらい 最小:316ぐらい

14 実験結果I(n依存性,m=4000) Qの直交性 || QTQ - I ||F 残差評価 || A - QR ||F
従来のハウスホルダー変換: 青 AllReduceアルゴリズム: 赤 AllReduce アルゴリズムは,従来法よりむしろ精度が良い

15 実験結果II(m依存性,n=100) Qの直交性 || QTQ - I ||F 残差評価 || A - QR ||F
従来のハウスホルダー変換: 青 AllReduceアルゴリズム: 赤 AllReduce アルゴリズムは,従来法よりむしろ精度が良い

16 数値実験2 乱数行列 A ∈Rm×n を Q ∈Rm×n と R∈Rn×n へ分解 行列サイズ: 4000×100 従来のハウスホルダー変換
AllReduceアルゴリズム 再帰の段数は最大5 (32分割) 行列サイズ: 4000×100 ||A||_F 最大:1290ぐらい 最小:316ぐらい

17 実験結果(再帰段数依存性) Qの直交性 || QTQ - I ||F 残差評価 || A - QR ||F
ハウスホルダー変換 ハウスホルダー変換 再帰段数を増やすことで,(この範囲では)精度が向上する

18 疑問点 AllReduceアルゴリズムでは,演算量が増加したにもか かわらず,精度がむしろ向上しているのはなぜか?
+要因: 計算を小さい行列のQR分解に帰着させることで,       内積のベクトル長が減少 ー要因: 2段階のQR分解により,誤差の蓄積が増大 それぞれの影響を定量的に評価するため,理論的解析が必要

19 理論的誤差解析 目標 AllReduce型QR分解における後退誤差の評価 計算で得られる Q の直交性の評価 : 計算で得られた上三角行列
  : 計算で得られた上三角行列   : 分解で使ったハウスホルダー変換を無限精度で蓄積した直交行列        を評価 計算で得られる Q の直交性の評価   :計算で得られた Q 考え方: 計算で得られたRに,計算途中で使ったハウスホルダー変換を無限精度でかけていったら,その結果がどれだけ元の行列に近くなるか。それを計るのがΔA。

20 AllReduceアルゴリズム(再掲) 解析に便利なように記法を変更 ここではまだ誤差のことは考えない 上付き添字は分解のステージを表す
下付き添字は行列の上半分/下半分を現す ここではまだ誤差のことは考えない n A1 Q1 (1) R1 (1) R1 R2 (1) Q(2) m A R A2 Q2 (1) (1) R2 (1) R(1)

21 後退誤差解析のための図式 Q(1) Q(1) Q(2) backward error exact exact computed

22 AllReduceアルゴリズム全体の後退誤差
各ステップでの後退誤差の式 後退誤差の評価 右辺の各項をそれぞれ評価する。 より, . AllReduceアルゴリズム全体での後退誤差

23     の評価 (I) 第1ステージの2個のQR分解の後退誤差 これより, により       を定義すると, . .

24 の評価 (II) ハウスホルダー変換に対する誤差評価(Higham, 1996)より, ただし, ( :マシンイプシロン) これより, .
  ただし,                ( :マシンイプシロン) これより, . .

25      の評価 同様に,ハウスホルダー変換に対する誤差評価の結果より, 次の式が成り立つ。 (∵ Q(1)は正確な直交行列) (前ページの結果より)

26 AllReduceアルゴリズム全体の後退誤差
     のとき,これは通常のハウスホルダーQR分解の後退 誤差       の半分程度の大きさとなる。   AllReduceアルゴリズムの高精度性に対する一つの説明

27 計算で得られる Q の直交性の評価 同様に,Q の直交性の誤差は次のように評価できる。
     のとき,これは通常のハウスホルダーQR分解におけ る直交性の誤差      の半分程度の大きさとなる。

28 まとめと今後の課題 まとめ 今後の課題 ハウスホルダーQR分解のためのAllReduceアルゴリズムの精 度を実験的・理論的に評価した
理論的誤差解析により,これを支持する結果を得た 今後の課題 再帰的に適用した場合の理論的誤差解析 並列環境での性能評価 二重対角化・三重対角化アルゴリズムへの組み込みと精度 評価


Download ppt "AllReduce アルゴリズムによる QR 分解の精度について"

Similar presentations


Ads by Google