Finger patternのブロック化による陰的wavelet近似逆行列前処理の高速化今倉暁曽我部知広張紹良名古屋大学大学院工学研究科計算理工学専攻 Outline  近似逆行列前処理  Wavelet近似逆行列前処理  Finger patternのブロック化 [提案法]  数値実験・結果  まとめ・今後の課題近似逆行列前処理近似逆行列前処理 偏微分方程式を離散化した際の線形方程式を前処理付きKrylov部分空間法で解くことを考える. 本研究では, 前処理として以下の近似逆行列前処理を扱う. M の計算. 最小二乗問題：M の j 番目の列ベクトル完全独立・並列化が容易： I の j 番目の列ベクトル近似逆行列前処理  実際に解く上で, M に要求される性質・・・計算コスト I. 疎行列である. II. が小さい. ・・・近似逆行列の精度 M の非零構造を考える. → A-1の構造を参考にする. 閾値：小フィルタリングを行う疎性と精度を両立させたい 0 値大閾値：大 0 小小 0 0 疎性： × 精度： ○ 値大疎性： ○ 精度： × Wavelet近似逆行列前処理 Wavelet近似逆行列前処理～離散wavelet変換（DWT）～ L : 任意パラメータ Wの非零構造 L = 3214 Wavelet近似逆行列前処理同値 0 0 W 0 0 0 0 Finger pattern Finger pattern (S. C. Hawkins and K. Chen, 2006) (T. F. Chan et al., 1997) 疎性と精度の両立が可能 Wavelet近似逆行列前処理近似逆行列前処理 Finger pattern 陰的wavelet近似逆行列前処理 Finger pattern Wavelet近似逆行列前処理～wavelet依存性～  DWTの精度に影響  近似逆行列の疎性に影響 Daubechies 4 影響が少ない 精度が高い 疎性が低い 計算コストが高い Haar 精度が低い 疎性が高い 計算コストが低い Time[s] Sherman 4 (n=1104) Watt 1 (n=1856) 1.2 0.4 0.4 1.2 1.1 1.0 0.9 0.3 0.8 0.7 0.2 0.6 0.5 0.4 0.3 0.1 0.2 0.1 0.0 前処理行列の構築時間反復法にかかる時間本研究では WaveletをHaarに限定する 116 85 1 Daubechies4 反復 128 87 回数 2 Haar Finger patternのブロック化 Finger patternのブロック化～従来法の問題点～近似逆行列の計算問題点近似逆行列の非零構造が列ごとに異なる為, 異なる部分行列に対して, QR分解を合計n 回行う必要がある. 陰的法を例に・・・最小二乗問題 QR分解の結果を再利用する為に, Finger patternのブロック化を提案する.  QR分解  後退代入本研究では, 陰的法に対してブロック化を行った. Finger patternのブロック化従来法 A(:,Sj) 提案法 mj(Sj) A(:,Sj) mj(Sj) Finger patternのブロック化～精度比較～の非零構造 Theorem 1. Proof. 従来法提案法数値実験・結果数値実験 Test行列 • Poisson3Da (electromagnetics problem) n = 13514, Nnz = 352726 • dw8192 (computational fluid dynamics problem) n = 8192, Nnz = 41746 前処理 • 陰的wavelet近似逆行列前処理[従来法] • 提案法 • ILU(0) 解法 • GMRES - 初期近似解 - 停止条件 T x0= (0,…,0) -8 |rn|/|r0| < 10 計算環境 • CPU • メモリ • コード : PowerPC G5 2.5GHz : 4.0GB : Fortran77 • コンパイラ : g77 –O5 T b = (1,…,1) 結果 poisson3Da QR分解後退代入 ILU(0)の分解 GMRES 12 12 158 158 159 159 160 160 反復回数 57 10 Time[s] 8 2.2倍 6 3.5倍 3.0倍 4 2 0 1.8倍 1.7倍 1.5倍 3 4 6 7 9 10 L= 1 3 2 5 8 4 5 従来法提案法従来法提案法従来法提案法 ILU(0) 結果相対残差 dw8192 ― 前処理なし ― 従来法 L=8 ― 提案法 L=6 ― 提案法 L=7 ― 提案法 L=8 ― ILU(0) ０反復回数５００結果 dw8192 QR分解後退代入 ILU(0)の分解 GMRES 25 25 Time[s] 20 15 指数関数的に計算時間は減少計算時間が増大 10 5 449 ０0 L= ６1 316 ７2 提案法 230 ８3 484 反復回数 4 ILU(0) まとめ・今後の課題まとめ・今後の課題 陰的wavelet近似逆行列前処理に対して, finger pattern のブロック化を行った. 最小二乗問題でのQR分解の結果を再利用することにより, 全体で約1.5倍高速化された. また, 従来法では収束しない問題に対しても収束する場合もみられた. 提案法は従来法に代わる有効な解法になり得る. 今後の課題 前処理行列の構築の更なる高速化 アルゴリズムの並列化及び実装