卒業論文発表

GPBi-CG法とBi-CGSTAB法を用いた
ハイブリッド型解法について
(平成１９年３月７日)
†名古屋大学工学部
†長井康幸
††名古屋大学工学研究科
††曽我部知広
††張紹良
目次
１．研究背景
・大規模疎行列を係数にもつ連立一次方程式の解法
２．研究目的
・数値解法（GPBi-CG法とBi-CGSTAB法の特徴を活かして）
３．本研究
・GPBi-CG法とBi-CGSTAB法を用いたハイブリッド型解法の提案
４．数値実験
５．まとめと今後の課題
研究背景
クリロフ部分空間法
A A
T
大規模疎行列を係数にもつ
連立一次方程式 Ax  b の反復解法.
CG法:共役勾配法(1952)
（拡張）
A A
Bi-CG法:双共役勾配法(1976)
（積型解法）
Bi-CGSTAB法(1992)
GPBi-CG法(1997)
T
研究目的
GPBi-CG法とBi-CGSTAB法の特徴.
◎
◎
○
○
○
◎
収束性
安定性
一反復
当たりの
演算量
・収束性,安定性に関して
4
GPBi-CG
0
Bi-CGSTAB
log 10
Bi-CGSTAB
法
rn
b
GPBi-CG
法
-12
0
研究目的
メリットを活かした解法
を目指す.
ハイブリッド型解法
1500
3000
反復回数
収束履歴の例
・一反復あたりの演算量に関して
係数行列の疎性にもよるが,１割から
２割程度,Bi-CGSTAB法の方が少ない.
GPBiCG(m,l)法 (Fujino,2002)
[既存の研究]
GPBiCG(m,l)法の流れ
…
…
m回
S
…
l回
S
G
…
m回
G
S
…
l回
S
G
G
…
do n=1,2,3,…（反復開始）
Bi-CGSTAB法
GPBi-CG法
pn, αn, yn, tn
pn, αn, yn, tn
残差ノルムの一次元最小化 z n
残差ノルムの二次元最小化z n, h n
un, zn, xn+1, rn+1, βn, wn
un, zn, xn+1, rn+1, βn, wn
end do
（反復の終端）
一反復当たりの演算量の削減 [本研究]
GPBiCG(m,l)[削減型]の流れ
…
S
…
S
S
G
…
G
S
…
S
S
G
…
G
…
do n=1,2,3,…（反復開始）
Bi-CGSTAB法
pn, αn,
GPBi-CG法
pn, αn, yn, tn
tn
残差ノルムの一次元最小化 z n
un zn xn+1, rn+1, βn,
wn
end do
残差ノルムの二次元最小化 z n, h n
un, zn, xn+1, rn+1, βn, wn
（反復の終端）
動的手法の提案 [本研究]
- GPBi-CG法とBi-CGSTAB法のハイブリッド型解法の提案 -
動的手法１
動的手法２
0
log 10
log 10
rn
b
rn
b
0
0
s
G
s
s
反復回数
組み合わせ方
if ｒn  ｒn－１
Bi-CGSTAB
else
GPBi-CG
end if
s
0
5
s
G
G
s
反復回数
組み合わせ方
if ｒn  ｒ j
then
残差ノルム
を抑える
GPBi-CG
end if
5
for all j < n then
Bi-CGSTAB
else
s
数値実験
・問題
係数行列を次の問題１,問題２のように設定し, b  1,1,...,1 を右辺項とした
連立一次方程式 Ax  b を解く.
T
問題１
問題２
Toeplitz行列
1
 2

2
1
 0
1.65 0
2
A
1.65 0


1.65


1
2
1
0
2
A  R10 10 , b  R10
6
6
6
非零要素数は299997.
・計算機
CPU
PowerPC G5 2.5GHz
メモリ 4 GB




,




Matrix Marketより取得した行列
SHERMAN5: 油層シュミレーション
を係数行列Ａとする.
A  R33123312 , b  R3312
非零要素数は20793.
停止条件
相対残差 log10
rn
b
 12.
演算量削減型を用いた結果（問題１）
GPBi-CG
Bi-CGSTAB
GPBiCG(2,1)
GPBiCG(2,1)[削減型]
log 10
rn
b
0
-12
演算時間
[秒]
1.40
0.00
0
1.2×10-2
GPBi-CG
反復回数
0.6×10-2
Bi-CGSTAB
100
1.1×10-2
0.8×10-2
GPBiCG(2,1)
GPBiCG(2,1)
[削減型]
・反復回数は丸め誤差の影響による.
・演算時間はGPBiCG(2,1)法[削減型]が少なかった.
演算量削減型を用いた結果（問題２）
4
GPBi-CG
Bi-CGSTAB
GPBiCG(2,1)
GPBiCG(2,1)
[削減型]
log 10
rn
b
0
-12
演算時間
[秒]
0.60
0.00
0
1.7×10-4
GPBi-CG
反復回数
1.5×10-4
Bi-CGSTAB
3000
1.9×10-4
GPBiCG(2,1)
1.6×10-4
GPBiCG(2,1)
[削減型]
・反復回数は丸め誤差の影響による.
・演算時間はGPBiCG(2,1)法[削減型]が同程度か,それ以下であった.
動的手法を用いた結果（問題１）
0
log 10
rn
b
GPBi-CG
Bi-CGSTAB
GPBiCG(2,1)[削減型]
動的手法１
動的手法２
-12
0
反復回数
100
演算時間
[秒]
1.40
85:30
1.2×10-2
0.00 GPBi-CG
0.6×10-2
Bi-CGSTAB
66:22
0.8×10-2
0.9×10-2
GPBiCG(2,1) 動的手法１
[削減型]
動的手法２
0.8×10-2
・反復回数は丸め誤差の影響による.
・演算時間は,演算量削減の効果もあり,動的手法が少なかった.
動的手法を用いた結果（問題２）
4
GPBi-CG
Bi-CGSTAB
GPBiCG(2,1)[削減型]
動的手法１
動的手法２
log 10
rn
b
0
-12
0
反復回数
3000
[秒] 0.60
2068:249
演算時間
949:1139
1.7×10-4
1.5×10-4
1.6×10-4
1.6×10-4
0.00 GPBi-CG Bi-CGSTAB GPBiCG(2,1)
動的手法１
[削減型]
1.8×10-4
動的手法２
・反復回数は丸め誤差の影響によるが、有効な場合もあった.
・演算時間は,演算量削減の効果もあり,動的手法が同程度か,それ以下であった.
まとめと今後の課題
まとめ
・Bi-CGSTAB法とGPBi-CG法のパラメータ切り替え時の演算量の削減が
可能であることを示した. （ GPBiCG(m,l)法の演算量削減につながる.）
・GPBiCG(m,l)法を用いてどの程度速くなるかを計算時間で比較,確認した.
さらに,
・Bi-CGSTAB法とGPBi-CG法を用いたハイブリッド型解法として,残差ノル
ムの大きさを比較する,動的手法を２通り提案した.
・動的手法が特定の問題に対しては有効であることがわかった.
今後の課題
・多くの問題で総合的な評価を行う.
・他の組み合わせ方を検討する.

Download Report