PARCEL SYCL v1.2 / 利用者ガイド 利用者ガイド API リファレンス 検索 ダウンロード English

6 ソルバの選び方

 解く問題の性質から, ソルバと前処理を選ぶ目安を示す. 各ソルバのアルゴリズムは「線形ソルバ」・「固有値ソルバ」・「前処理」の各章に示す. C言語・Fortran から選べるソルバは「使用方法」の章に示す.


6.1 線形ソルバ

 まず係数行列AAが対称正定値かどうかで分ける.

行列 第一の候補 次の候補
対称正定値 (前処理行列KKも対称正定値) pcg pgmres (前処理が対称でない場合など)
非対称, または対称だが正定値でない pgmres またはpbicgstab ランク数が多く集団通信が律速する場合はpcagmres

 各ソルバの特徴を次に示す.

ソルバ 1 反復の主な演算 保持するベクトル 特徴と注意
pcg SpMV 1 回, 前処理 1 回 少数 (固定) AAとKKが対称正定値であることが前提. 最も軽い. 収束判定は漸化式の残差
pbicgstab SpMV 2 回, 前処理 2 回 少数 (固定) 非対称行列向け. 残差は単調に減るとは限らない. ⟨r*,q⟩=0\langle r^{\ast},q \rangle = 0などで破綻しうる (DIVERGED_BREAKDOWN). 内積の精度Tdotを FP16 にすると, 精度の下限に近い判定値で破綻しやすい. 収束判定は漸化式の残差
pgmres SpMV 1 回, 前処理 1 回, 直交化 リスタート周期mmに比例 (基底m+1m + 1本) 1 回のリスタートの中では残差ノルムを最小化する. 既定はm=30m = 30 (基底 31 本). 難しい問題ではset_restart()で増やし, メモリが足りない場合は減らす. 収束判定はリスタートの先頭の真の残差だけで行うので, 反復上限に達した場合を除き反復回数はmmの倍数になる. 直交化は既定の修正 Gram-Schmidt 法 (QR_MGS) では基底 1 本ごとに内積の集団通信を行い, QR_CGSではそれらを 1 回にまとめる
pcagmres ss回の SpMV・前処理をまとめてから直交化 ststに比例 数学的には GMRES(stst) と同等で, 集団通信の回数を減らす. 既定はs=8s = 8, t=4t = 4 (GMRES(32) 相当) で, set_restart(s, t)で変える. ssが大きいと単項式基底が悪条件になり, GMRES より収束が悪くなる. FP16 のデータ精度・計算精度では Cholesky QR 系を使わない. set_explicit_q(CAGMRES_Q_IMPLICIT)では正規直交基底を陽に作らず, 基底の Gram 行列の Cholesky 分解だけで直交化する (集団通信は基底ブロックあたり 1〜2 回). このとき直交性の誤差は基底の条件数の 2 乗に比例するので, ssを大きくするとQR_MGSより早く悪化しうる. QR_CAGMRES_CHOLESKYQRはAAが対称・前処理なし・ssが偶数の場合に限る (AAの対称性は検査しない)

 目安は次のとおりである.


6.2 固有値ソルバ

 3 つの固有値ソルバはいずれも標準固有値問題Ax=λxAx = \lambda xを扱い, 一般化固有値問題は扱わない. 求めたい固有値で選ぶ.

求めたいもの ソルバと設定 注意
絶対値最大の固有値 1 個 power 収束の速さは絶対値最大と 2 番目の固有値の比で決まる. 比が 1 に近いと遅い
絶対値最小の固有値 1 個 inverse_power 各反復で内部の線形ソルバを解く. AAが対称で正定値 (または負定値) ならset_linsolve_algo(parcel::krylov::LINSOLVE_PCG)で内部をpcgにできる
シフトσ\sigmaに近い固有値 (内部の固有値) ks_arnoldiの shift-invert (set_shift(σ)と第 4 引数のA−σIA - \sigma I) 計算時間の大半は内部のpgmresが占める. σ\sigmaを固有値に近づけるとリスタート回数は減るが, A−σIA - \sigma Iの条件数が悪くなり内部のpgmresが重くなる
複数の固有値, 複素共役対の固有値 ks_arnoldi set_ks_subspace(m, k_keep, nev)で部分空間の大きさと判定対象の数を指定する. 出力のnev個を超える分は収束を保証しない
絶対値最小の固有値が複素共役対, または非対称で絶対値最小側を複数 ks_arnoldiの shift-invert をσ=0\sigma = 0で inverse_powerは実数の Rayleigh 商を用いるので複素共役対に収束しない
前処理後の行列AK−1AK^{-1}の条件数 powerとinverse_powerにset_precon_spectrum(true) 両端の固有値の比を取る. AK−1AK^{-1}の固有値は 1 付近に密集しやすく, powerの収束は遅くなる

 powerとinverse_powerは, 求める側の端の固有値が複素共役対の場合と, 絶対値の等しい固有値が複数ある場合 (例えば±λ\pm\lambda) には収束しない. そのような行列にはks_arnoldiを使う.

 inverse_powerと shift-invert の内部の線形ソルバは, 外側とは別にset_linsolve_tolerance()・set_linsolve_max_iteration()・set_linsolve_precon_algo()などで設定する. 内部の前処理の既定は Jacobi 前処理 (反復 1 回) である. 内部の反復が多い場合はset_linsolve_precon_algo()・set_linsolve_jacobi()で前処理を替える, または強める. 内部の収束の確かめ方は「収束状態の確かめ方」に示す.

6.2.1 set_precon_spectrum() の意味

 固有値ソルバでは, 前処理は「どの行列の固有値を求めるか」を変える.

 AAの固有値が欲しい場合にset_precon_algo()だけを指定しても, 外側の反復は速くならない. 各ソルバでの前処理の使われ方は, べき乗法・逆べき乗法・Krylov-Schur 法の各節の表に示す.


6.3 前処理

前処理 1 回の適用の費用 通信 前処理の作用と MPI 分割 向いている場面
なし (0) なし なし — 前処理の効果を比べる基準. set_precon_algo()の既定 (固有値ソルバの内部線形ソルバの既定は Jacobi 前処理)
ポイント Jacobi (1) nn回の乗算 なし 分割によらない 最も安価. 効果は小さい
ブロック Jacobi (2) ブロック内の前進・後退代入 なし ランク数と分割数nbnbで変わる CPU (既定のブロック数はランクあたりのスレッド数)
Jacobi (4) SpMV をITER回 (set_jacobi()) Jacobi 反復ごとに袖通信 分割によらない GPU. 各行が独立に計算できる