Accelerated algorithm for Principal Components

AllReduce アルゴリズムによる
QR 分解の精度について
山本有作 森大介 張紹良
名古屋大学 大学院工学研究科 計算理工学専攻 張研究室
行列・固有値の解法とその応用 第6回研究会
2008/11/26
目次
QR分解
QR分解の並列化アルゴリズム




従来のハウスホルダー変換
AllReduceアルゴリズム
精度に関する数値実験
理論的誤差解析
まとめと今後の課題



2
QR分解
行列 A ∈Rm×n を Q ∈Rm×n と R ∈Rn×n に分解する



Q: 列直交行列
R: 上三角行列
n
m
A = Q
R
応用例
m≫n
最小二乗問題
特異値分解の前処理
二重対角化・三重対角化のブロック化アルゴリズム
電子状態計算
大規模問題に対する高速かつ高精度な手法が必要
3
QR分解
グラムシュミットの直交化法



並列化に向く(古典的グラムシュミット法)
得られるQ の直交性は行列の条件数に依存
ハウスホルダーQR分解



4
計算が逐次的
得られるQ の直交性が良い
(従来の)ハウスホルダー変換
あるベクトル x を任意のベクトル y に変換する

H
x
0
A
H1
作成
H2
作成
0
H1
y
u  x  x 2 e1 → u を正規化
(I: 単位行列)
H  I  2uuT
 H 1  H T  H
0 0
H2
作用
作用
H N ・・・
H3 H 2 H1
A 
R
QT
各ステップの計算は逐次的なため
並列化(高速化)が困難
5
Q  H1H 2 H3 ・・・
H N
A = QR
並列化時に考えるべき点
プロセッサ間の通信量


通信量が大きいと(計算以外の)コストが増加
通信回数



通信回数が多くても(計算以外の)コストが増加
(通信にかかる全時間)
= (データ通信時間)+(立ち上げ時間)
tcomm
≪
tsetup
通信回数の少ないアルゴリズムが必要
以下,分散メモリ型の並列計算機を考える
6
ハウスホルダー変換の並列化 (2並列)
n
行列を上下に二分割して
各プロセッサにデータを持たせる。

u  x  x 2 e1
→ u を正規化
(I: 単位行列)
H  I  2uu
1
T
H H H
m
T
H
A
0 0
I. u の生成(||x||2 の計算)
II. H = I -
2uuT の作用
各ステップ
2回
communication
0
communication
7
update
合計
2N 回
AllReduceアルゴリズム*(Langou 2007)
n
: それぞれ独立に計算可能
A1
m

Q1 R1
R1
A
A2

Q2 R2
R
communication
m≫n
QR分解はすべて
ハウスホルダー変換で行う
• m/2×n の行列 2回
• 2n×n の行列 1回
合計
1回
A 
Q1 O
O Q2
8
R2


~
Q
~
Q
R

Q
R


このアルゴリズムは再帰的に利用可能
再帰段数が増えるにつれ,計算量は従
来のハウスホルダー変換に比べて増加
* TSQR(Tall and Skinny QR)アルゴリズムとも呼ばれる
比較
従来の
ハウスホルダー変換
手法
計
算
量
逐次
計算
2 3
2MN  N  OMN 
3
2MN 2  2 N 3  OMN 
並列
計算
1 3
MN  N  OMN 
3
8 3
MN  N  OMN 
3
2N
1
1 2
N N
2
1 2
N
2
通信回数
通信量
9
AllReduce
アルゴリズム
2
2
2
計算量と計算時間(逐次計算)
計算量
8  2  10 3
2MN 
N
3
 OMN 
QR分解の計算時間
k
1.5
2
k は再帰の段数
計算時間 (s)

1
0.5
0
0
1
2
3
4
5
再帰の段数(k )
ハウスホルダー変換
CPU: Xeon 2.80GHz
メモリ: 4GB
行列サイズ: 4000×100
10
本研究の目的


並列性能についてはすでに多くの検証がなされている
(Demmel et al. 2008,村上 2008)
精度についてはまだ詳細な報告がない
AllReduce アルゴリズムの精度を実験的・理論的に評価する

11
演算量の増加が精度にどのような影響を及ぼすか?
数値実験概要

精度の指標



直交性
残差
実験項目

従来のハウスホルダー変換と
2分割のAllReduceアルゴリズムの精度比較



|| QTQ - I ||F
|| A - QR ||F
行列サイズ(m, n)依存性
AllReduceの再帰段数を変えたときの精度比較
計算機環境



12
CPU
Xeon 2.80GHz
メモリ
4GB
コンパイラ GNU C/C++ Compiler
数値実験1

乱数行列 A ∈Rm×n を Q ∈Rm×n と R∈Rn×n へ分解
1.
2.

従来のハウスホルダー変換
AllReduceアルゴリズム
再帰の段数は1で固定(2分割)
行列サイズ
m
I 4000
II 1000~5000
13
n
100~500
100
実験結果I(n依存性,m=4000)
残差評価 || A - QR ||F
Qの直交性 || QTQ - I ||F
1.00E-12
1.00E-11
1.00E-13
1.00E-12
1.00E-14
1.00E-13
100
200
300
400
N
500
100
200
300
400
N
従来のハウスホルダー変換: 青
AllReduceアルゴリズム: 赤
AllReduce アルゴリズムは,従来法よりむしろ精度が良い
14
500
実験結果II(m依存性,n=100)
Qの直交性 || QTQ - I ||F
残差評価 || A - QR ||F
1.00E-12
1.00E-11
1.00E-13
1.00E-12
1.00E-14
1.00E-13
1000
2000
3000
4000
M
5000
1000
2000
3000
4000
M
従来のハウスホルダー変換: 青
AllReduceアルゴリズム: 赤
AllReduce アルゴリズムは,従来法よりむしろ精度が良い
15
5000
数値実験2

乱数行列 A ∈Rm×n を Q ∈Rm×n と R∈Rn×n へ分解
1.
2.

従来のハウスホルダー変換
AllReduceアルゴリズム
再帰の段数は最大5 (32分割)
行列サイズ: 4000×100
16
実験結果(再帰段数依存性)
残差評価 || A - QR ||F
Qの直交性 || QTQ - I ||F
1.00E-12
1.00E-11
1.00E-13
1.00E-12
1.00E-14
1.00E-13
0
1
2
3
再帰の段数
ハウスホルダー変換
4
5
0
1
2
3
再帰の段数
ハウスホルダー変換
再帰段数を増やすことで,(この範囲では)精度が向上する
17
4
5
疑問点

AllReduceアルゴリズムでは,演算量が増加したにもか
かわらず,精度がむしろ向上しているのはなぜか?
+要因: 計算を小さい行列のQR分解に帰着させることで,
内積のベクトル長が減少
ー要因: 2段階のQR分解により,誤差の蓄積が増大
それぞれの影響を定量的に評価するため,理論的解析が
必要
18
理論的誤差解析

目標

AllReduce型QR分解における後退誤差の評価




: 計算で得られた上三角行列
: 分解で使ったハウスホルダー変換を無限精度で蓄積した直交行列
を評価
計算で得られる Q の直交性の評価


:計算で得られた Q
を評価
AllReduceアルゴリズム(再掲)

解析に便利なように記法を変更



上付き添字は分解のステージを表す
下付き添字は行列の上半分/下半分を現す
ここではまだ誤差のことは考えない
n
A1
m

(1)
Q(1)
R
1
1
A
(1)
R1
(1)
A2

(1)
Q2 R2(1)
R2
R(1)

~(2)
Q R
Q
後退誤差解析のための図式
backward
error
Q(1) exact
Q(1)
exact
Q(2)
exact
computed
backward
error
computed
AllReduceアルゴリズム全体の後退誤差

各ステップでの後退誤差の式
より,
.
AllReduceアルゴリズム全体での後退誤差

後退誤差の評価

右辺の各項をそれぞれ評価する。
の評価 (I)

第1ステージの2個のQR分解の後退誤差
により
を定義すると,
.

これより,
.
の評価 (II)

ハウスホルダー変換に対する誤差評価(Higham, 1996)より,
ただし,

.
( :マシンイプシロン)
これより,
.
の評価

同様に,ハウスホルダー変換に対する誤差評価の結果より,
次の式が成り立つ。
(∵ Q(1)は正確な直交行列)
(前ページの結果より)
AllReduceアルゴリズム全体の後退誤差

以上より,AllReduceアルゴリズム全体の後退誤差は次のよう
に評価できる。

のとき,これは通常のハウスホルダーQR分解の後退
の半分程度の大きさとなる。
誤差
AllReduceアルゴリズムの高精度性に対する一つの説明
計算で得られる Q の直交性の評価

同様に,Q の直交性の誤差は次のように評価できる。

のとき,これは通常のハウスホルダーQR分解におけ
る直交性の誤差
の半分程度の大きさとなる。
まとめと今後の課題

まとめ




ハウスホルダーQR分解のためのAllReduceアルゴリズムの精
度を実験的・理論的に評価した
AllReduceアルゴリズムでは,従来のハウスホルダー変換に
比べ,誤差がむしろ小さくなる傾向が見られた
理論的誤差解析により,これを支持する結果を得た
今後の課題



28
再帰的に適用した場合の理論的誤差解析
並列環境での性能評価
二重対角化・三重対角化アルゴリズムへの組み込みと精度
評価