メモリ使用量の少ないGCR法の提案 東京大学理学部情報科学科 工藤 誠 東京大学情報基盤センター 黒田 久泰 東京大学理学部情報科学科 工藤 誠 東京大学情報基盤センター 黒田 久泰 東京大学大学院理学系研究科情報科学専攻 片桐 孝洋 東京大学情報基盤センター 金田 康正

連立一次方程式の解法 大規模疎行列を係数行列に持つ連立一次方程式 反復解法、特にKrylov部分空間法がポピュラー SYMMLQ GMERR Bi-CG QMR CGS Bi-CGSTAB GMRES MINRES GCR CG Method The minimum error approach petrov-Galerkin approach The minimum residual approach Ritz-Galerkin approach Approach Krylov部分空間法の分類

GCR法の特徴 GCR法の利点 広範囲の非対称問題が解ける 逐次成分がなく、並列性が高い CG法の非対称問題への拡張として開発された[Eisenstat, 83] Arnoldi原理に基づき、各反復で残差を最小にする （GMRES法と数学的に同値な残差） GCR法の利点 広範囲の非対称問題が解ける 逐次成分がなく、並列性が高い GMRESR法[Vorst,91]の一部として使われている

GCR法の 問題点 計算量大！ メモリ使用量大！ 計算量が大きい（O(k 2N)の計算が３回） メモリ使用量が大きい（GMRESの約２倍） 連立一次方程式 を解くGCR(k)法のアルゴリズム 計算量大！ メモリ使用量大！

過去の研究 計算量を減らすefficient GCR(eGCR)法が考案された[Yang,95] しかし、依然としてメモリ使用量が大きい という問題は解決されていない！！

提案する２つのアルゴリズム Memory efficient GCR(meGCR)法 Unrolled GCR(uGCR)法

Efficient GCR法 Originalの GCR法

Efficient GCR法 各反復で解ｘを ループの外に 出した 方向ベクトルpはここにしか表れない また、pをApを使って表すことができる

さらに、uもApを使って表すことができる Efficient GCR法 Efficient GCR pの計算が 無くなった ベクトルuは、過去の分まで覚えておく ^ さらに、uもApを使って表すことができる ^

メモリ使用量は既存のアルゴリズムの約半分！ Memory efficient GCR法 覚えておくベクトルはApのみでよい 係数行列、解ベクトル以外の メモリ使用量は既存のアルゴリズムの約半分！ 計算量はeGCR法と同程度 ベクトルuを使用しない ^

Air0はdominantな固有ベクトルの Unrolled GCR法 ループ内で使われている値は、 すべてAir0を使って表すことができる ループの前で、Air0を計算しておく ループ内の計算で必要な(Air0, Ajr0)も 計算しておく Air0はdominantな固有ベクトルの 方向を向いてくるので、 精度の低下が予想される 密行列積（BLAS3）の演算となり、 効率的 ループ内はスカラー計算のみとなる メモリ使用量は meGCRと同じ

計算量の比較 * 1リスタート周期の計算量 dmv dp smv prec bin kmv 2kn 2n 3(k-1) 2k 2k-1 k 密行列-ベクトル積 (k X nの) 密行列-密行列積 サイズnの 密行列-ベクトル積 1リスタート周期の計算量 計算要素 dmv dp daxpy smv prec bin kmv Dmm 計算量 2kn 2n * GCR 3(k-1) 2k 2k-1 k eGCR 1 meGCR k+1 2 uGCR 4k 注 *は、問題や前処理の 方法によって変わってくる k = リスタート周期(数十～数百) n = 問題サイズ (数万～数百万)

メモリ使用量の比較1 （係数行列、解ベクトル以外） Vector of length n Buffer of size k 2 GCR 2k+3 eGCR 2 meGCR k+3 uGCR k+2 5 既存の手法の 約半分！ k = リスタート周期(数十～数百) n = 問題サイズ (数万～数百万)

メモリ使用量の比較2 (係数行列、解ベクトルを含んだ全体のメモリ使用量) method 全体のメモリ使用量 GCR eGCR meGCR uGCR k = リスタート周期(数十～数百) n = 問題サイズ (数万～数百万) z = 係数行列の一行の最大非零要素

実験環境 計算機: HITACHI SR2201 通信ライブラリ：MPI (Message Passing Interface) （東京大学情報基盤センター） CPU: 300MFlops × 1024PE Main memory: 256MB/PE Communication: 300MB/s 通信ライブラリ：MPI (Message Passing Interface)

Problems Problem 1 Problem 2 Problem3 Toeplitz行列 楕円型偏微分方程式の境界値問題（２次元） 楕円型偏微分方程式の境界値問題（３次元）

meGCR法の実験結果(逐次) 実行時間（秒） リスタート周期32 問題 Problem 1 Problem 2 Problem 3 サイズ 実行時間（秒） リスタート周期32 問題 Problem 1 Problem 2 Problem 3 サイズ 400,000 160,000 64,000 前処理無し GCR 22.8 4860 37.8 eGCR 18.3 3440 27.7 meGCR 17.9 3450 28.7 前処理有り (B-ILU(0)) 21.2 938 21.9 19.8 812 19.9 20.1 825

meGCR法の実験結果（並列、前処理なし） Problem 1 ( n=4,000,000 ) Problem 2 ( n=160,000 ) Problem 3 ( n=512,000 ) リスタート周期はすべて３２

meGCR法の実験結果（並列、B-ILU(0)前処理） Problem 1 ( n=4,000,000 ) Problem 2 ( n=160,000 ) Problem 3 ( n=512,000 ) リスタート周期はすべて３２

uGCR法の実験結果 リスタート周期 8 前処理無し B-ILU(0)前処理 Iteration Time Problem 1 GCR 46 リスタート周期 8 前処理無し B-ILU(0)前処理 Iteration Time Problem 1 (n=400,000) GCR 46 18.5 17 20.3 eGCR 15.4 18.2 meGCR 19.5 uGCR 55 13.5 25 26.7 Problem 3 (n=64,000) 1096 64.8 150 30.6 53.6 29.6 55.7 31.7 1053 43.0 30.1

まとめと考察 GCR法の２つのアルゴリズムを提案した Memory efficient GCR法 Unrolled GCR法 より大きな問題が解ける リスタート周期を大きく 取れるので、収束の悪い 問題が解ける GCR法の２つのアルゴリズムを提案した Memory efficient GCR法 計算量は、既存の方法とほぼ同じ メモリ使用量は、最高で既存の方法の約半分まで減らすことが可能 Unrolled GCR法 計算量、メモリ使用量とも既存の方法より少ない 収束性に問題がなく、実用的！ 精度の問題があるので、今後の研究が必要