Fill-in LevelつきIC分解による 前処理について 染原一仁 † 藤野清次 ‡ †　九州大学大学院システム情報科学府 ‡　九州大学情報基盤センター

発表の手順 研究の背景、目的 前処理技法 数値実験 まとめ IC(tol)分解 :閾値によるドロッピング IC(p)分解 :fill-in levelによるドロッピング 数値実験 まとめ そしてその並列化について説明します． 今回はこのようなことに着目しました．

研究の背景、目的 大規模な連立一次方程式 Ax = b を前処理つき共役勾配(CG)法で高速に解きたい (行列Aは対称正定値行列) 　～背景～ 大規模な連立一次方程式 Ax = b を前処理つき共役勾配(CG)法で高速に解きたい　(行列Aは対称正定値行列) CG法の収束性を高めるために前処理が併用して用いられることが多く，その種類は様々である 　～目的～ 棄却判定の異なる2つのIC分解(IC(tol)分解，IC(p)分解)によって得られる前処理行列を適用したICCG法の収束性評価を行う．

M-1Ax=M-1b 前処理(1) 連立一次方程式Ax=bに前処理行列M を以下のように作用させる 係数行列M-1Aが単位行列 I に近似される |λ(M-1A)| 固有値の重複，密集 反復法の収束性向上

前処理(2) 対角スケーリング(CG法に適用) IC分解(前処理つきCG法に適用) 前進(後退)代入 行列ベクトル積

A = LLT + R + RT (L-1AL-T) (LTx) = (L-1b) IC（不完全コレスキー）分解 係数行列が対称な場合に適用可能。 以下のように係数行列A を近似分解する。 A = LLT + R + RT 前処理行列M = LLT を作用させる。 (L-1AL-T) (LTx) = (L-1b) 下三角行列 棄却行列 計算時間小、使用メモリ量小⇒実用的。

IC(tol)分解 lij < tol lij = 0 閾値(tolerance)を用いたドロッピングによるIC分解 前処理行列の非零要素数が予測できない

IC(p)分解(1) levij > p lij = 0 Fill-in levelを用いたドロッピングによるIC分解 levij = min{levij, levik+levkj+1} levij = min{levij, max(levik,levkj)+1} (Y.Saad, Iterative methods for Sparse Linear Systems, 2003) 係数行列Aの非零要素パターンによりFill-inの深さを探索 IC(0)分解では前処理行列Lの非零要素数と係数行列Aの下三角部分は等しくなる

IC(p)分解(2) IC(1) 分解 IC(0) 分解 係数行列:A 行列:L

数値実験 計算機 ：IBM eServer p5 モデル 595 CPU ：IBM POWER5 (1CPU使用) クロック周波数 ：1.9 GHz メモリ容量 ：3 GB プロセッサ/メモリ 間帯域幅(ピーク時) ：811.0GBps キャッシュサイズ ：1.9MB コンパイラ ：IBM XL Fortran version 9.1 オプション ：-O3 -qarch=pwr5 -qtune=pwr5 -qhot

計算条件 計算は全て倍精度演算 プログラム言語はfortran90を使用 前処理つきCG法の収束判定は相対残差 ||rk+1||/||r0|| < 10-12 初期近似解 x0 はすべて 0 固有値計算は数値計算ライブラリLAPACKを使用 テスト行列はフロリダ大学，Matrix Marketのデータベース， http://www.cise.ufl.edu/research/sparse/matrices/index.html http://math.nist.gov/MatrixMarket/

実験に用いた解法 (反復法はすべてCG法) 前処理 DIAG 対角スケーリングのみ適用 SIC(tol) DIAG+シフトつきIC(tol)分解 SIC(p) DIAG+シフトつきIC(p)分解 IC分解途中に対角要素が負にならないようにシフトを適用 A+αIを分解(α：シフト量)，今回は0.2に固定 条件数:cond=||A|| ||A-1|| = (最大固有値) / (最小固有値) 実対称正定値行列

テスト行列(1) 次元数：1万以下 行列 次元数 下三角部分の非零要素数 半帯幅 分野 bcsstk15 3,948 60,882 437 sts4098 4,098 38,227 3,323 nasa4704 4,704 54,730 423 bcsstk16 4,884 147,631 140 構造解析 Muu 7,102 88,618 4,696 Kuu 173,651 4,697 bcsstk38 8,032 181,746 6,029

行列bcsstk15 非零要素パターン 次元数 ：3,948 非零要素数：60,882 半帯幅 ：437

IC(tol)分解による 行列Lの非零要素パターン 非零要素数 = 15,125 tol = 0.005 非零要素数 = 53,518

IC(p)分解による 行列Lの非零要素パターン 非零要素数 = 60,882 p = 1 非零要素数 = 126,535

IC(p)分解による 行列Lの非零要素パターン 非零要素数 = 60,882 p = 2 非零要素数 = 191,225

行列bcsstk15 次元数：3,948 条件数：6.54×109 tol=0.1 p=0 p=1 p=2 tol=0.005

行列bcsstk15 (条件数:6.54×109) 解法 閾値/level Lの非零要素数 条件数 反復回数 DIAG - 8.21×104 665 0.1 15,125 8.55×103 217 SIC(tol) 0.05 21,525 4.71×103 174 0.01 41,149 4.04×103 161 0.005 53,518 3.93×103 159 60,882 5.77×103 187 SIC(p) 1 126,535 4.18×103 163 2 191,225 3.89×103 158

行列sts4098 次元数：4,098 条件数：2.17×108 tol=0.1 p=0 p=1 p=2 tol=0.005

行列sts4098 (条件数:2.17×108) 解法 閾値/level Lの非零要素数 条件数 反復回数 DIAG - 6.72×103 547 0.1 14,782 3.62×102 137 SIC(tol) 0.05 21,235 3.07×102 119 0.01 36,714 2.52×102 115 0.005 46,369 38,227 4.20×102 140 SIC(p) 1 389,651 2.65×102 117 2 1,051,689 2.53×102 114

テスト行列(2) 次元数：5万以上 行列 次元数 下三角部分の 非零要素数 半帯幅 分野 nasasrb 54,870 1,366,097 893 s3dkt3m2 90,449 1,921,955 614 構造解析 shipsec8 114,919 3,384,159 4,627 bmwcra_1 148,770 5,396,386 141,050 thremal2 1,228,045 4,904,179 1,226,000 熱解析 G3_circuit 1,585,478 4,623,152 947,128 回路問題

各前処理つきCG法の収束性 行列:nasasrb

IC(p)CG法の収束性 行列:nasasrb

行列nasasrb 次元数：54,870 解法 閾値/level 行列Lの 非零要素数 反復回数 計算時間 [sec] DIAG - 19,779 118.11 SIC(tol) 0.05 481,328 5,573 59.83 0.01 940,936 4,821 66.93 SIC(p) 1,366,097 4,360 75.88 1 2,192,348 3,852 108.88

各前処理つきCG法の収束性 行列:G3_circuit

各前処理つきCG法の収束性 行列:G3_circuit

行列G3_circuit 次元数：1,585,478 解法 閾値/level 行列Lの 非零要素数 反復回数 合計時間 [sec] DIAG - 3,299 328,54 SIC(tol) 0.01 6,741,212 1,022 253.61 0.005 7,554,105 1,013 262.54 SIC(p) 4,623,152 1,181 267.93 1 6,075,667 1,044 253.29 2 7,817,649 1,014 264.53

行列6ケース(合計時間) 行列 解法 閾値/level 反復回数 合計時間 nasasrb IC(tol) 0.05 5,573 59.83 s3dkt3m2 0.1 12,102 186.21 shipsec8 0.005 1,743 66.63 bmwcra_1 2,013 113.53 thermal2 0.01 2,067 506.03 G3_circuit IC(p) 1 1,044 253.29

まとめ 次元数5万以上の行列において6ケース中5ケースはIC(tol)分解によるICCG法の計算時間が最も短くなった． Fill-in levelによるIC(p)分解では許容するlevelを大きくすることにより，L-1AL-Tの条件数は1に近づき，ICCG法の収束性は向上する． しかし，行列Lの非零要素数が多くなり，収束までの計算時間は増加する．

固有値分布 bcsstk15

固有値分布 sts4098