6 ソルバの選び方
解く問題の性質から, ソルバと前処理を選ぶ目安を示す. 各ソルバのアルゴリズムは「線形ソルバ」・「固有値ソルバ」・「前処理」の各章に示す. C言語・Fortran から選べるソルバは「使用方法」の章に示す.
6.1 線形ソルバ
まず係数行列が対称正定値かどうかで分ける.
| 行列 | 第一の候補 | 次の候補 |
|---|---|---|
| 対称正定値 (前処理行列も対称正定値) | pcg |
pgmres (前処理が対称でない場合など) |
| 非対称, または対称だが正定値でない | pgmres またはpbicgstab |
ランク数が多く集団通信が律速する場合はpcagmres |
各ソルバの特徴を次に示す.
| ソルバ | 1 反復の主な演算 | 保持するベクトル | 特徴と注意 |
|---|---|---|---|
pcg |
SpMV 1 回, 前処理 1 回 | 少数 (固定) | とが対称正定値であることが前提. 最も軽い. 収束判定は漸化式の残差 |
pbicgstab |
SpMV 2 回, 前処理 2 回 | 少数 (固定) | 非対称行列向け. 残差は単調に減るとは限らない. などで破綻しうる (DIVERGED_BREAKDOWN). 内積の精度Tdotを FP16 にすると, 精度の下限に近い判定値で破綻しやすい. 収束判定は漸化式の残差 |
pgmres |
SpMV 1 回, 前処理 1 回, 直交化 | リスタート周期に比例 (基底本) | 1 回のリスタートの中では残差ノルムを最小化する. 既定は (基底 31 本). 難しい問題ではset_restart()で増やし, メモリが足りない場合は減らす. 収束判定はリスタートの先頭の真の残差だけで行うので, 反復上限に達した場合を除き反復回数はの倍数になる. 直交化は既定の修正 Gram-Schmidt 法 (QR_MGS) では基底 1 本ごとに内積の集団通信を行い, QR_CGSではそれらを 1 回にまとめる |
pcagmres |
回の SpMV・前処理をまとめてから直交化 | に比例 | 数学的には GMRES() と同等で, 集団通信の回数を減らす. 既定は, (GMRES(32) 相当) で, set_restart(s, t)で変える. が大きいと単項式基底が悪条件になり, GMRES より収束が悪くなる. FP16 のデータ精度・計算精度では Cholesky QR 系を使わない. set_explicit_q(CAGMRES_Q_IMPLICIT)では正規直交基底を陽に作らず, 基底の Gram 行列の Cholesky 分解だけで直交化する (集団通信は基底ブロックあたり 1〜2 回). このとき直交性の誤差は基底の条件数の 2 乗に比例するので, を大きくするとQR_MGSより早く悪化しうる. QR_CAGMRES_CHOLESKYQRはが対称・前処理なし・が偶数の場合に限る (の対称性は検査しない) |
目安は次のとおりである.
- 対称正定値なら
pcgを使う. 対称でも正定値でない場合はpcgの前提を満たさないので, 非対称向けのソルバを使う. - 非対称では, メモリに余裕があり収束を安定させたい場合は
pgmres, 1 反復を軽くしたい場合はpbicgstabを試す.pbicgstabがDIVERGED_BREAKDOWNで止まる場合はpgmresに替える. - 通信削減型 (
pcagmres) は, 多数のランクでMPI_Allreduceの待ちが支配的になる場合に, 集団通信の回数を減らすためのものである. 丸め誤差に対してはpgmresより弱いので, 既定のでpgmresより反復回数が大きく増える, または収束しない場合はを小さくする.pgmresと同じ反復回数で収束することを確かめてからを増やす. - 収束したかどうかは
is_converged()とget_converged_reason()で確かめる.pcg・pbicgstabでは, 解の精度はget_true_residual()(真の残差) で確かめる (「数値精度と再現性」). pcgは既定で探索方向を 1 本だけ持つ. メモリに余裕があれば, 実行時にPARCEL_PSTEP=4とすると解の更新をまとめて少し (1〜3%) 速くなる (「メモリと速さの選択」).
6.2 固有値ソルバ
3 つの固有値ソルバはいずれも標準固有値問題を扱い, 一般化固有値問題は扱わない. 求めたい固有値で選ぶ.
| 求めたいもの | ソルバと設定 | 注意 |
|---|---|---|
| 絶対値最大の固有値 1 個 | power |
収束の速さは絶対値最大と 2 番目の固有値の比で決まる. 比が 1 に近いと遅い |
| 絶対値最小の固有値 1 個 | inverse_power |
各反復で内部の線形ソルバを解く. が対称で正定値 (または負定値) ならset_linsolve_algo(parcel:で内部をpcgにできる |
| シフトに近い固有値 (内部の固有値) | ks_arnoldiの shift-invert (set_shift(σ)と第 4 引数の) |
計算時間の大半は内部のpgmresが占める. を固有値に近づけるとリスタート回数は減るが, の条件数が悪くなり内部のpgmresが重くなる |
| 複数の固有値, 複素共役対の固有値 | ks_arnoldi |
set_ks_subspace(m, k_keep, nev)で部分空間の大きさと判定対象の数を指定する. 出力のnev個を超える分は収束を保証しない |
| 絶対値最小の固有値が複素共役対, または非対称で絶対値最小側を複数 | ks_arnoldiの shift-invert をで |
inverse_powerは実数の Rayleigh 商を用いるので複素共役対に収束しない |
| 前処理後の行列の条件数 | powerとinverse_powerにset_precon_spectrum(true) |
両端の固有値の比を取る. の固有値は 1 付近に密集しやすく, powerの収束は遅くなる |
powerとinverse_powerは, 求める側の端の固有値が複素共役対の場合と, 絶対値の等しい固有値が複数ある場合 (例えば) には収束しない. そのような行列には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() の意味
固有値ソルバでは, 前処理は「どの行列の固有値を求めるか」を変える.
set_precon_spectrum(false)(既定): の固有値を返す.set_precon_algo()などの前処理の設定は外側の固有値反復に使わない.inverse_powerと shift-invert で内部の線形ソルバを速くしたい場合は,set_linsolve_precon_algo()などで別に指定する (返す固有値はの固有値のまま).set_precon_spectrum(true): 前処理後の行列の固有値を返す. はset_precon_algo()などの設定でから作る. 前処理の性能評価 (のスペクトルと条件数) に用いる.
の固有値が欲しい場合にset_precon_algo()だけを指定しても, 外側の反復は速くならない. 各ソルバでの前処理の使われ方は, べき乗法・逆べき乗法・Krylov-Schur 法の各節の表に示す.
6.3 前処理
| 前処理 | 1 回の適用の費用 | 通信 | 前処理の作用と MPI 分割 | 向いている場面 |
|---|---|---|---|---|
| なし (0) | なし | なし | — | 前処理の効果を比べる基準. set_precon_algo()の既定 (固有値ソルバの内部線形ソルバの既定は Jacobi 前処理) |
| ポイント Jacobi (1) | 回の乗算 | なし | 分割によらない | 最も安価. 効果は小さい |
| ブロック Jacobi (2) | ブロック内の前進・後退代入 | なし | ランク数と分割数で変わる | CPU (既定のブロック数はランクあたりのスレッド数) |
| Jacobi (4) | SpMV をITER回 (set_jacobi()) |
Jacobi 反復ごとに袖通信 | 分割によらない | GPU. 各行が独立に計算できる |
- GPU では Jacobi 前処理を第一の候補とする. ブロック Jacobi 前処理は GPU の並列度を確保するためにブロックを数行まで細かくする必要があり (既定は 1 ブロック 2 行), 多くの場合 Jacobi 前処理の方が速い.
- Jacobi 前処理は既定ではメモリを節約するための値を持たず, 適用のたびに計算する. GPU のメモリに余裕があれば,
-DPARCEL_JACOBI_ONTHEFLY=0でビルドすると前処理が速くなる (NX=512・4 装置のpcgで 1 反復が V100 14%, MI300A 23% 短い. 「メモリと速さの選択」). - ブロック Jacobi 前処理の作用はランク数と分割数で変わるので, ランク数を変えると反復回数も変わる. ランク数を変えて結果を比べる場合は, Jacobi 前処理またはポイント Jacobi 前処理を使う.
pcgはが対称正定値であることを前提とする. ブロック Jacobi 前処理は行列スケーリングが有効な場合にとなるため, 行ごとの最大絶対値が揃っていない行列ではが対称でなくなりうる (前処理の章のブロック Jacobi 前処理). 検証用サンプルではPARCEL_PRECON_SYMCHECK=1でを確かめられる.- 低精度と組み合わせる場合の制約 (FP16 の前処理とポイント Jacobi 前処理の組合せなど) は「数値精度と再現性」に示す.