Finger patternのブロック化による 陰的wavelet近似逆行列前処理の 高速化

Presentation on theme: "Finger patternのブロック化による 陰的wavelet近似逆行列前処理の 高速化"— Presentation transcript:

1 Finger patternのブロック化による 陰的wavelet近似逆行列前処理の 高速化
今倉　暁　　曽我部　知広　　張　紹良 名古屋大学　大学院工学研究科　計算理工学専攻

2 Outline 近似逆行列前処理 Wavelet近似逆行列前処理 Finger patternのブロック化 [提案法] 数値実験 ・ 結果
まとめ ・ 今後の課題

3 近似逆行列前処理

4 近似逆行列前処理 偏微分方程式を離散化した際の線形方程式 を前処理付きKrylov部分空間法で解くことを考える.
本研究では, 前処理として以下の近似逆行列前処理を扱う. M の計算. 最小二乗問題 完全独立・並列化が容易 ：M の j 番目の列ベクトル ： I の j 番目の列ベクトル

5 M の非零構造を考える. → A-1の構造を参考にする.
近似逆行列前処理 実際に解く上で, M に要求される性質 疎行列である. 　　　　　 　が小さい. ・・・計算コスト ・・・近似逆行列の精度 M の非零構造を考える. → A-1の構造を参考にする. 疎性と精度を両立させたい フィルタリングを行う 閾値　：　小 閾値　：　大 値 値 大 小 大 小 疎性　：　× 精度　：　○ 疎性　：　○ 精度　：　×

6 Wavelet近似逆行列前処理

7 Wavelet近似逆行列前処理 ～離散wavelet変換（DWT）～ L : 任意パラメータ Wの非零構造 4 L = 2 L = 1

8 Wavelet近似逆行列前処理 W 同値 疎性と精度の両立が可能 Finger pattern Finger pattern
(S. C. Hawkins and K. Chen, 2006) Finger pattern (T. F. Chan et al., 1997) 同値 W 疎性と精度の両立が可能

9 Wavelet近似逆行列前処理 近似逆行列前処理 Finger pattern 陰的wavelet近似逆行列前処理

10 Wavelet近似逆行列前処理 ～wavelet依存性～ DWTの精度に影響 近似逆行列の疎性に影響 1.2 116 128 0.4
Time[s] 近似逆行列の疎性に影響 Watt 1 (n=1856) 1.2 116 128 Sherman 4 (n=1104) 0.4 前処理行列 の構築時間 反復法にかかる 時間 影響が少ない Daubechies 4 精度が高い 疎性が低い 計算コストが高い 本研究では WaveletをHaarに限定する Haar 精度が低い 疎性が高い 計算コストが低い 反復回数 85 87 Daubechies4 Haar

11 Finger patternのブロック化

12 Finger patternのブロック化 ～従来法の問題点～ 近似逆行列の計算 問題点 近似逆行列の非零構造が
　　近似逆行列の非零構造が 　　列ごとに異なる為, 異なる 　　部分行列に対して, QR分解 　　を合計n 回行う必要がある. 陰的法を例に・・・ 最小二乗問題 QR分解の結果を再利用する為に, Finger patternのブロック化を提案する. 本研究では, 陰的法に対してブロック化を行った. QR分解 後退代入

13 Finger patternのブロック化 従来法 提案法 A(:,Sj) mj(Sj) A(:,Sj) mj(Sj)

14 Finger patternのブロック化 ～精度比較～ の非零構造 Theorem 1. Proof. 従来法　　提案法

15 数値実験・結果

16 数値実験 Test行列 Poisson3Da (electromagnetics problem) 前処理
dw8192 (computational fluid dynamics problem) n = 13514, Nnz = n = , Nnz = T b = (1,…,1) 前処理 陰的wavelet近似逆行列前処理[従来法] 提案法 ILU(0) 解法 GMRES 初期近似解 停止条件 T x = (0,…,0) |r |/|r | < 10 -8 n 計算環境 CPU : PowerPC G5 2.5GHz メモリ : 4.0GB コード : Fortran77 コンパイラ : g77　–O5

17 結果 poisson3Da QR分解 後退代入 ILU(0)の分解 GMRES 12 Time[s] 3.5倍 3.0倍 2.2倍 1.8倍
反復回数 158　 158 159　 159 160　 160 57 Time[s] 3.5倍 3.0倍 2.2倍 1.8倍 1.7倍 1.5倍 L= 3 4 5 従来法　提案法 従来法　提案法 従来法　提案法 ILU(0)

18 結果 dw8192 ― 前処理なし ― 従来法 L=8 ― 提案法 L=6 ― 提案法 L=7 ― 提案法 L=8 ― ILU(0) 相 対
残 差 ― 前処理なし ― 従来法　L=8 ― 提案法　L=6 ― 提案法　L=7 ― 提案法　L=8 ― ILU(0) ０ 反復回数 ５００

19 結果 dw8192 QR分解 後退代入 ILU(0)の分解 GMRES 25 指数関数的に 計算時間が増大 指数関数的に 計算時間が増大
計算時間は減少 Time[s] 449 316 230 449 316 230 484 反復回数 ０ L= ６ ７ ８ 提案法　 　　　　 ILU(0)

20 まとめ・今後の課題

21 まとめ ・ 今後の課題 陰的wavelet近似逆行列前処理に対して, finger pattern のブロック化を行った.
最小二乗問題でのQR分解の結果を再利用すること　により, 全体で約1.5倍高速化された. また, 従来法では収束しない問題に対しても収束す　る場合もみられた. 提案法は従来法に代わる有効な解法になり得る. 今後の課題 前処理行列の構築の更なる高速化 アルゴリズムの並列化及び実装