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

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

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

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

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 ・・・

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

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

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）アルゴリズムとも呼ばれる

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

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

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

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

数値実験１ 乱数行列 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ぐらい

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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