複数右辺ベクトルをもつ連立一次方程式に対する!
高速・高精度 Block Krylov アルゴリズムの開発
多田野寛人
筑波大学システム情報系
A01 高橋班
新学術領域研究「コンピューティクスによる物質デザイン」"
平成23年
年度第1回回研究会"
年10月月8日日
2011年

複数の右辺ベクトルをもつ連立一次方程式§1 はじめにL 本の右辺ベクトルをもつ連立一次方程式
AX = B

ここで，A ∈ C n×n ：n 次非 Hermite 行列，"�� (1) (2)�
� (1) (2)(L)(L)
, B = b ,b ,...,bX = x ,x ,...,x

応用例""周周回積分を用いた固有値解法（Sakurai-Sugiura法法）"
台形則による周回積分の近似で現れる""""格
格子 QCD 計算における物理量計算"
L = 12〜〜数百 の連立一次方程式の求解が必要"「コンピューテ
年度第1回回研究会"" ィクスによる物質デザイン」平成23年

2011年
年10月月8日日

 1 !

Block Krylov 部分空間反復法
Block Krylov 部分空間反復法の性質§1 はじめに

1. !L 本の方程式をまとめて解くことができる．"
本ずつ解いた場合よりも"
2. "Krylov 部分空間法で 1本"少少ない反復回数で残差が収束することがある．"
3. "収
収束判定条件が満たされた場合でも，近似解の"精度が要求精度からかけ離れている場合がある．"
Block BiCGGR法
法 を開発し克服．

弱点

L が大きい場合は残差が発散することが多い！
「コンピューティクスによる物質デザイン」平成23年
年度第1回
回研究会

2011年
年10月月8日日

 2 !

本研究の目的§1 はじめに1.! Block BiCGGR 法の数値的不安定性を除去する"方法を考案する．""方開発した方法の数値的安定性を確かめる．!
2. "開「コンピューティクスによる物質デザイン」平成23年
年度第1回
回研究会

2011年年10月月8日日

 3 !

Block BiCGGR法
法の長所と不安定性の原因§2 Block BiCGGR法
法n×LX0 ∈ C
is an initial guess,
Compute R0 = B − AX0 ,Set P0 = R0 ,Choose R̃0 ∈ C n×L ,For k = 0, 1, . . . , until �R�F ≤ ε�B�F do:HAP)α=R̃
R for α k ,Solve ( R̃H
kk00 ktr[(AR k )H R k ],ζk =H
tr[(AR k ) AR k ]U k = (P k − ζ k AP k )α k ,X k+1 = X k + ζ k R k + U k ,R k+1 = R k − ζ k AR k − AU k ,HSolve ( R̃HR /ζ for γ k ,R)γ=R̃
kk
00 k+1 k
P k+1 = R k+1 + U k γ k ,AP k+1 = AR k+1 + AU k γ k ,End For

長所"
近似解の精度劣化を防ぐように"漸化式が構築されている"
不安定性の原因"
反復過程で現れる n # L 行列の"線形独立性が失われ，小規模"連立一次方程式が悪条件問題"になるため"「コンピューティクスによる物質デザイン」平成23年
年度第1回回研究会

2011年
年10月月8日日

 4 !

Block BiCGGR法
法の残差の振る舞い§2 Block BiCGGR法
法残差が発散！

Fig. 1. Block BiCGGR法
法の相対残差履歴．"■：L = 1，，■：L = 2，，■：L = 4."，■：L = 8，，■：L = 12．
．"「コンピューティクスによる物質デザイン」平成23年
年度第1回
回研究会

2011年
年10月月8日日

 5 !

残差行列の直交化による Block BiCGGR 法の安定化§3 Block BiCGGR法
法の安定化

数値的不安定性を回避するには反復過程で現れる n#L 行列の線形独立性の回復が必要"
反復過程で行列の直交化を行うようにする
本研究では…
Block BiCGGR法
法の残差行列 Rk を"
R k = Q k ξ k , QHk Q k = I L , ξ k ∈ C L×L"と直交化するアルゴリズム Block BiCGGRRO法
法 を構築した"「コンピューティクスによる物質デザイン」平成23年
年度第1回
回研究会

2011年
年10月月8日日

 6 !

Block BiCGGRRO法
法のアルゴリズムX0 ∈ C n×L is an initial guess,
Compute Q0 ξ0 = B − AX0 ,Set S0 = Q0 ,Choose R̃0 ∈ C n×L ,For k = 0, 1, . . . , until �ξ k �F ≤ ε�B�F do:
HSolve ( R̃HAS)α=R̃
Q for α k ,kk
00 k§3 Block BiCGGR法
法の安定化直交化を実行"ζ k = arg min �Q k ξ k − ζ AQ k ξ k �F ,
ζV k = (S k − ζ k AS k )α k ,��
X k+1 = X k + ζ k Q k + V k ξ k ,Q k+1 τ k+1 = Q k − ζ k AQ k − AV k ,ξ k+1 = τ k+1 ξ k ,HQ)γ=R̃
Q /ζ for γ k ,Solve ( R̃Hkk
00 k+1 k

S k+1 = Q k+1 + V k γ k ,AS k+1 = AQ k+1 + AV k γ k ,End For

残差行列の直交化により"行列の線形独立性が"n # L行保持されると期待される"「コンピューティクスによる物質デザイン」平成23年
年度第1回
回研究会

2011年
年10月月8日日

 7 !

問題設定と実験内容§4 数値実験"

解く問題
格子量子色力学（QCD））計算で現れる"
連立一次方程式："
AX = Bn = 1, 572, 864，，nnz(A) = 80, 216, 064，，"
行あたりの非零要素数は 51．
．
1行Fig. 2.

非零構造図．

実験内容
1. "Block BiCGGR法
法とBlock BiCGGRRO法
法の性能比較"直交化回数の削減による高速化と解法に与える影響の検証"
2. "直「コンピューティクスによる物質デザイン」平成23年
年度第1回回研究会

2011年
年10月月8日日

 8 !

実験環境と実験条件
Table 1. 実験環境．
CPU
MemoryCompilerCompile option§4 数値実験"

AMD Opteron 6180 SE 2.5GHz × 4
256.0GBytes
PGI Fortran ver. 11.5-O3 -tp=x64 -mp

Table 2. 実験条件．
Initial solution X0
Right hand side B
Shadow residual R̃0
Stopping criterion[0, 0, . . . , 0][e1 , e2 , . . . , e L ]Random number�R k �F /�B�F ≤ 1.0 × 10−14or �R k �F /�B�F ≥ 1.0 × 106「コンピューティクスによる物質デザイン」平成23年
年度第1回
回研究会

2011年
年10月月8日日

 9 !

Block BiCGGR法
法と Block BiCGGRRO法
法の比較§4 数値実験"(a) Block BiCGGR法
法．

(b) Block BiCGGRRO法
法．

Fig. 3. 2つつの解法の相対残差履歴の比較．"，■：L = 2，，■：L = 4，，■：L = 8，，■：L = 12．
．"■：L = 1，
「コンピューティクスによる物質デザイン」平成23年
年度第1回
回研究会

2011年
年10月月8日
日  10 !

直交化回数の削減による高速化§4 数値実験"

計算量削減による高速化
Block BiCGGRRO法
法では，反復毎に n#L 行列の直交化を"行っている．L が大きい場合は多くの計算時間を要する．"
直交化を毎回実行せずに，一定反復回数毎に行うことで"計算時間を短縮できないか？

直交化を施したBlock BiCGSTAB法
法（前回の研究会で講演）と"法で直交化回数削減の影響を調査した．"
Block BiCGGRRO法「コンピューティクスによる物質デザイン」平成23年
年度第1回回研究会

2011年
年10月月8日
日  11 !

直交化回数を減少させたときの影響（反復回数）§4 数値実験"

残差は収束せず"直交化の実行間隔"に依らず収束"）．"
Fig. 4. 直交化の実行間隔が反復回数に及ぼす影響（L = 8）●：Block BiCGGRRO法
法，●：直交化付きBlock BiCGSTAB法
法．"「コンピューティクスによる物質デザイン」平成23年
年度第1回
回研究会

2011年
年10月月8日
日  12 !

直交化回数を減少させたときの影響（解の精度）§4 数値実験"

残差が発散"

高精度近似解が"得られている"

Fig. 5. 直交化の実行間隔が解の精度に及ぼす影響（L = 8））．"●：Block BiCGGRRO法
法，●：直交化付きBlock BiCGSTAB法
法．"「コンピューティクスによる物質デザイン」平成23年
年度第1回
回研究会

2011年
年10月月8日
日  13 !

直交化回数を減少させたときの影響（計算時間）§4 数値実験"

直交化回数の減少で"高速化が可能！"

Fig. 6. 直交化の実行間隔が計算時間に及ぼす影響（L = 8））．"●：Block BiCGGRRO法
法，●：直交化付きBlock BiCGSTAB法
法．"「コンピューティクスによる物質デザイン」平成23年
年度第1回
回研究会

2011年
年10月月8日
日  14 !

まとめ

1.! Block BiCGGR 法を安定化した Block BiCGGRRO 法を""開開発した．"

2.! 残差行列の直交化により，Block BiCGGR法法の"収収束性""をを安定化することができた．"

3.! 直交化を毎回行わなくても近似解の精度や収束性に"与える影響は少なく，直交化付きBlock BiCGSTAB法
法""よよりもロバストであることが分かった．"

今後の課題
1. "直直交化の発動タイミングの自動化による高速化"

2. "他
他の問題での性能検証"