行列の対角優位置換による反復法の収束性評価およびそ

行列の対角優位並び換えによる反復法の
収束性評価およびその指標について
土持秀之九州大学大学院
藤野清次九州大学情報基盤センター
1
発表の手順
• 研究の背景と目的
• 反復法の収束性と行列の要素の並び換え
– 対角優位並び換え(Diagonal Dominant Permutation)
– MC64(Duff, Koster 1999, 2001)の概要
– 対角優位化の指標
• 数値実験
• まとめと今後の課題
2
研究の背景と目的
• 背景
– 行列要素の並換手法として，n/o(natural ordering), RCM
(Reverse Cuthill-McKee), MD(Minimam Degree)などがあ
る
– 近年，Duff(1999, 2001)らにより対角優位を図った並び換え
手法が提案(MC64と呼ばれる)された
– Duffらの協力により，MC64の効果を評価する機会を得る
• 目的
– MC64により，どのような行列が反復法の効果があるかを見極
める
– さらに，行列の要素の情報だけで，静的に，効果を予測する指
3
標についての考察を試みる
並び換え手法の例(RCMとDDP)
-1.5e+19
+9.3e+18
行列MCCA(Florida)
-1.5e+19
-1.0
+9.3e+18
RCMオーダリング
+1.0
RCMでは並び換えのみ
MC64では，対角要素が
絶対値の大きい値(+1, -1)
になるように並び換える
MC64
対角優位並び換え(Diagonal Dominant Permutation)と呼ぶ
4
対角優位並び換え手法(一般的)
• すべての列において，対角要素の絶対値 a
と非対角要素の絶対値 a の最大値との比
a
m ax a
jj
ij
jj
i j
ij
を大きくする並び換え手法
• 具体的には，元の行列Aから，並び換え行列P
が生成され，右からAP のように掛ける
 p  1,
 ij

 pij  0,
(i, j)  (i' , j' ) | a
i' j'

0
otherwise
5
並び換え行列P について
• いろいろな並び換え行列
– 対角要素をすべて非零要素にする並び換え行列P
の中で，最小の対角要素が最大となる並び換え行
列Pmax1 を選択
– 対角要素の絶対値の和を最大にする並び換え行列
Pmax2 を選択
• MC64の並び換え行列
– 対角要素の絶対値の積を最大にする並び換え行列
Pmax3 を選択
6
MC64の概要
• 対角要素の絶対値の積を最大にする
• 元の行列Aに対して，並び換え行列P の他に，
行と列に対するスケーリング行列Dr ,Dcが
考案され，
Dr A DcP
と左右から掛ける
7
元の行列Aと変換行列の例
A=
7
6
5


1 9



3
8


6
2 4

3

1
2


P=
1



 1

1



1 



1


Dr =
Dc =
1

7

9

1


7

36



1

5










9
7
1
7
6
7








5

3










1

8
8
変換後の対角優位性
A=
7
6
5


1 9



3
8


6
2 4

3

1
2


Dr A DcP =
3


1
1
4


1 1

 3

1
7


7


1
1
90 

5
 5
1 

12
 21

ave.=0.70
ave.=1.07
ave. =
| a jj |
max | aij |
の平均値
i j
9
変換後の行列の特徴
• 対角要素の絶対値がすべて1に，非対角要
素の絶対値がすべて1以下になる
a
jj
 1, aij  1
• すべての列において，対角要素の絶対値と
最大の非対角要素の絶対値との比が1以上
になる
a
jj
1
max aij
i j
10
対角要素に零要素を含む行列に
対するMC64の適用
• 前処理つき反復法では，対角要素に零要素があると
反復計算が途中で終了し，解を得ることができない
対角要素に零要素がある行列の例
行列LHR01の
非零要素パターン
行列WEST2021の
非零要素パターン
• MC64により，対角要素をすべて非零要素に換え，
11
反復計算を行う
行列LHR01に対するMC64の適用
-0.60
+0.93
元の行列
-1.0
+1.0
MC64後の行列
12
行列WEST2021に対するMC64の適用
-35136
+2050
元の行列
-1.0
+1.0
MC64後の行列
13
計算機環境と反復法
• 計算機環境
– 計算機 : IBM eServer p5 モデル 595
– CPU
: POWER5(1.9GHz)
– 主記憶 : 2TBytes
– OS
: IBM AIX 5L
– コンパイラ : IBM XL Fortran version 9.1
• 前処理
– ILU(0)分解：閾値不要
– ILUC(Crout ILU)分解：閾値あり
• 反復法
– すべてBiCGSafe法
14
計算条件とテスト行列
•
計算条件
– 最大反復回数:15000回
– 収束判定条件:相対残差ベクトルr 2ノルム
||rm||2/||r0||2 ≦ 10-7
– 右辺項ベクトルbは，以下のように作成
Ax=b, x=(1,2,…,n)T (n:次元数，T:行列の転置)
•
テスト行列の出典
– Matrix Market, Florida Matrix Collection
15
対角要素に零要素がある行列
行列
次元数
非零要素数
対角零解析分野
LHR01
1,477
18,427
1,452 化学工学
WEST2021
2,021
7,310
2,016 化学工学
BAYER09
3,083
11,767
3,079 化学シミュレーション
HCIRCUIT
105,676
513,072
48 回路シミュレーション
• 前処理
– ILU(0)分解：閾値不要
– ILUC(tol)分解：閾値あり
16
対角要素に零要素がある行列
に対するMC64の効果
閾値
反復
回数
並換
時間
前処理
時間
反復
時間
合計
時間
ILUC
all
break
-
-
-
-
あり
ILUC
0.01
5
0.01
0.02
0.01
0.04
無し
ILUC
all
break
-
-
-
-
あり
ILUC
0.01
3
0.01
0.04
0.00
0.05
無し
ILU(0)
無
break
-
-
-
-
あり
ILU(0)
無
97
0.30
0.11
2.11
2.52
無し
ILU(0)
無
break
-
-
-
-
あり
ILU(0)
無
17
0.02
0.01
0.01
0.04
行列
優位化
前処理
LHR01
無し
WEST2021
HCIRCUIT
BAYER09
時間の単位はすべて秒
17
対角要素に零要素が無い行列
に対するMC64の適用
行列
優位化
反復
回数
並換
時間
前処理
時間
反復
時間
合計
時間
K3PLATES
無し
4871
0.00
0.13
27.50
27.63
あり
3011
0.12
0.12
17.08
17.32
無し
907
0.00
0.10
13.88
13.98
あり
296
0.19
0.09
4.53
4.81
無し
527
0.00
0.72
8.28
9.00
あり
598
0.25
0.72
9.48
10.45
無し
10
0.00
0.03
0.07
0.10
あり
10
0.09
0.04
0.06
0.19
BCIRCUIT
SME3DA
ZHAO1
• MC64を適用しても，収束性にばらつきがある
前処理はすべて
18
ILU(0)分解
対角優位性と収束性向上の関係
• 上の関係を明らかにするため，対角要素の絶対値
と非対角要素の絶対値 aij の最大値との比
a
a
jj
max a ij
i j
をj 列の優位率と呼ぶ
• 元の行列と並び換えた後の行列に対するすべての列
の優位率の平均値を計算した
19
jj
優位率の検証のための行列
行列
次元数
非零要素数
対角零解析分野
K3PLATES
11,107
378,927
0 構造解析
BCIRCUIT
68,902
375,558
0 回路シミュレーション
SME3DA
12,504
874,887
0 構造解析
ZHAO1
33,861
166,453
0 電磁気学
• 前処理
– ILU(0)分解のみ：閾値不要
20
優位率の検証
優位率
の平均
反復
回数
並換
時間
K3PLATES 無し
1.27
4871
0.00
0.13 27.50 27.63
あり
1.65
3011
0.12
0.12 17.08 17.32
無し
25.35
907
0.00
0.10 13.88 13.98
あり
25.35
296
0.19
0.09
4.53
4.81
無し
3.10
527
0.00
0.72
8.28
9.00
あり
3.10
598
0.25
0.72
9.48 10.45
無し
10.81
10
0.00
0.03
0.07
0.10
あり
3.30
10
0.09
0.04
0.06
0.19
行列
BCIRCUIT
SME3DA
ZHAO1
優位化
前処理
時間
反復
時間
合計
時間
• 優位率の平均が増加した場合のみ収束性向上
と相関がある
前処理はすべて
ILU(0)分解
21
tolerance
Original
MC64
0.0
0.0
0.0
0.0
0.0
22
0.1
00
95
90
85
80
75
70
Original
65
0.0
05
0.0
10
0.0
15
0.0
20
0.0
25
0.0
30
0.0
35
0.0
40
0.0
45
0.0
50
0.0
55
0.0
60
0.0
65
0.0
70
0.0
75
0.0
80
0.0
85
0.0
90
0.0
95
0.1
00
00
Iterations
SME3DA
0.0
95
0.1
K3PLATES
60
90
0.0
例2
0.0
55
85
0.0
例1
0.0
MC64
50
45
tolerance
0.0
0.0
例3
40
• 閾値を用いるILUC(tol)分
解の場合，閾値によって
MC64の評価が定め難い
0.0
80
0.0
0
35
75
0.0
0
0.0
70
0.0
2000
30
65
0.0
2000
0.0
60
0.0
4000
25
55
0.0
4000
0.0
50
0.0
10000
20
45
0.0
10000
0.0
40
0.0
12000
15
35
0.0
14000
12000
0.0
30
0.0
14000
0.0
25
0.0
16000
10
20
0.0
6000
05
15
0.0
16000
0.0
Original
Iterations
10
0.0
8000
0.0
05
0.0
0.0
Iterations
ILUC(tol)分解のときのMC64の閾値依存性
8000
6000
tolerance
MC64
BCIRCUIT
600
500
400
300
200
100
0
まとめと今後の課題
• 対角要素に零要素を持つ行列でも，MC64による
対角優位化により，BiCGSafe法が収束するよう
になる
• 対角優位性と収束性向上の関係を調べた
すなわち，各行列の優位率を計算し，優位率が
増加した場合のみ収束性が向上する
• MC64と良く適合する前処理や反復法の調査
23
参考文献
• Duff, I. S., Koster, J., SIAM J. Matrix Anal.
Appl. Vol. 20, pp. 889-901, 1999.
• Duff, I. S., Koster, J., SIAM J. Matrix Anal.
Appl. Vol. 22, pp. 973-996, 2001.
• MC64の技術マニュアル(Ver. 1.3.0), 2005.
24

Download Report