10 前処理
一般に反復解法では, となるように前処理行列を選ぶと, 収束に必要な反復回数が減少する. アルゴリズムに見られる「」型の計算は「をについて近似的に解く」ことに相当する. この近似の精度を上げれば反復回数が減少するが, 逆にこの部分の計算のオーバーヘッドが増加する. 並列計算でない場合には, この近似計算に不完全LU分解を用いることが多いが, 並列計算の場合には, 前処理計算の並列処理手法が必要となる. 本ライブラリルーチンでは並列前処理法としてポイント Jacobi 法, ブロック Jacobi 法, Jacobi 法を採用している. 記号の約束は線形ソルバの章の冒頭に示したとおりである.
前処理はソルバのset_precon_algo()に次の値を与えて選ぶ. サンプルプログラムではコンパイル時に-Dparcel_solver_precon_algo=<値>で, 実行時に環境変数PARCEL_PRECON=<値>で指定できる.
| 値 | 定数 | 前処理 | 付随する設定 |
|---|---|---|---|
| 0 | parcel::PRECON_NONE |
前処理なし () | なし |
| 1 | parcel::PRECON_POINTJACOBI |
ポイント Jacobi 前処理 | なし |
| 2 | parcel::PRECON_BLOCKJACOBI |
ブロック Jacobi 前処理 (ブロック内 ILU(0)) | set_blockjacobi(nb), set_scaling_matrix(), set_scaling_vector() |
| 4 | parcel::PRECON_JACOBI |
Jacobi 前処理 | set_jacobi(ITER), set_scaling_matrix(), set_scaling_vector() |
以下では係数行列を (は対角部分, ・は狭義下三角・狭義上三角部分) と分解し, と書く. 各アルゴリズムは前処理の 1 回の適用「」の中身を示す.
10.1 スケーリング
ブロック Jacobi 前処理と Jacobi 前処理には, 行列スケーリングとベクトルスケーリングを併用できる. いずれも値の範囲を低精度 (半精度) の表現範囲に収めるための処理である. set_scaling_matrix()・set_scaling_vector()で明示的に指定でき, 指定しない場合は次のように自動で決まる.
ブロック Jacobi 前処理: 行列・ベクトルとも常に有効
Jacobi 前処理: 前処理の演算精度または前処理行列の格納精度が半精度の場合のみ有効 (倍精度・単精度では無効)
行列スケーリング: 各行の最大絶対値から を求め, で行をスケーリングする.
ベクトルスケーリング: 前処理の入力を (行列スケーリング無効時は) で割ってから前処理を適用し, 結果にを掛けて戻す. 線形な操作なので前処理の作用を変えない.
行列スケーリングがどの前処理の作用を変えるかは各節で述べる.
10.2 ポイント Jacobi 前処理 [1]
前処理行列として係数行列の対角成分のみを用いる (). 不完全LU分解など他の前処理法と比べると効果は小さいが, 各行が独立に処理でき, プロセッサ間通信も不要である. 対角成分が 0 の行はの対角要素を 1 に置き換える. スケーリングは行わない.
選択方法:
set_precon_algo(parcel::PRECON_POINTJACOBI)(値 1)アルゴリズム
はの対角要素, はの対角要素, は各 MPI プロセスが担当する行数である.
1〜7 行目は前処理行列の作成時に 1 回だけ行う. 前処理の適用は次のとおりである.
10.3 Jacobi 前処理 [1]
Jacobi 前処理は, を Jacobi 反復で近似的に解く PARCEL 独自の前処理である. 1 反復内の各行に依存性がないため GPU 向けの前処理である. 反復回数はset_jacobi(ITER)で指定する (既定 1. サンプルプログラムではコンパイル時に-DJACOBI_ITER=<値>).
- 選択方法:
set_precon_algo(parcel::PRECON_JACOBI)(値 4) とset_jacobi(ITER)
前処理行列の作成時にを求めて保持する (の行はの要素を 1 とする). の値は既定では (A64FX 向けのビルドを除き) 保持せず, 5 行目での値とからをその場で計算する (前処理行列の精度への丸めは保持する場合と同じなので値は同じ. メモリを使って速くする場合の-DPARCEL_JACOBI_ONTHEFLY=0は「メモリと速さの選択」). 全ての行に対角要素が格納されている必要がある. PARCEL はこれを検査しないので, 対角要素が格納されていない行があると前処理の結果は不正になる. 前処理の適用は次のとおりである. はベクトルスケーリング無効時は 1 である.
- アルゴリズム
5 行目はと同じであり, 反復は初期値から始まる. したがって作用は で, ゼロ初期値からの Jacobi 反復 (減衰係数 1) を回行ったものに等しい. でもであり, ポイント Jacobi 前処理 () とは異なる.
は係数行列の行ポインタと列番号を複製せずに共有する. 値を保持する場合 (-DPARCEL_JACOBI_ONTHEFLY=0, または下の対象外の場合) は, 値だけをと同じ並び (対角の位置は 0) で持つ. 5 行目では行ごとに控えた対角の位置で対角を飛ばす. 既定では前処理を適用するたびにの値も読む. 各ソルバは前処理をsolver()の中で作り, solver()の中だけで使う (固有値ソルバの内部線形ソルバも同じ) ので, 通常の使い方ではsolver()の実行中にを破棄・変更しなければよい (solver()を呼ぶたびに作り直すので, 呼び出しの間にの値を変えるのは構わない). 前処理行列parcel::precon_matrixを直接作って使う場合 (pgmresのexternal_preconなど. 通常は使わない) は, 使い終えるまでを破棄・変更してはならない. (既定) では反復用の作業ベクトルを確保しない.
の値をその場で計算する対象は, CRS 形式の行列で, 行列スケーリングが無効で, 係数行列・前処理行列・前処理の演算精度のいずれも double-double でない場合である. 半精度 (FP16) の前処理は行列スケーリングが既定で有効になるので, 値を保持する. 対象外の場合は-DPARCEL_JACOBI_ONTHEFLY=0と同じく値を保持する.
MPI 並列時は 5 行目の前に (1 回目は) の袖領域を通信する. は通信込みの大域行列として定まるため, 前処理の作用は MPI の分割数によらない.
行列スケーリング有効時は, からとを作り, 2 行目でにを掛ける. とが同じ係数で割られるためとは変わらず, 前処理の作用は変わらない (丸め誤差を除く).
10.4 ブロック Jacobi 前処理 [1]
前処理行列として係数行列のブロック対角成分をとり, 各ブロック内でフィルイン無し不完全LU分解 (ILU(0)) を用いる. ブロックの外にある要素は無視する. 各 MPI プロセスが担当する行を連続する個のブロック (行数はまたは) に分割するため, ブロックがプロセスをまたぐことはなく, 通信は不要で, 各ブロックは完全に並列に処理できる. 一方で前処理の作用は MPI の分割数とに依存する.
- 選択方法:
set_precon_algo(parcel::PRECON_BLOCKJACOBI)(値 2). 分割数はset_blockjacobi(nb)で指定する. 指定しない場合は, CPU では MPI プロセスあたりのスレッド数, GPU では 1 ブロック 2 行となる値 () を用いる.
ILU(0) は, 正方行列を下三角行列と上三角行列の積に近似分解する際に, の非零要素の位置 (非零パターン) 以外に値が入ること (フィルイン) を許さない不完全LU分解である. フィルインを考慮しないことで, 分解後の行列のメモリ使用量を元の行列と同じに抑えられる.
- アルゴリズム (前処理行列の作成. ブロック内 ILU(0))
・はブロックの先頭行と最終行, はの非零パターンである. はの要素の複製を上書きしていく.
分解後, ブロック内の狭義下三角部分と対角要素 1 から (単位下三角行列) を, 対角を含む上三角部分からを作る.
- アルゴリズム (前処理の適用)
・は・の要素, は行列スケーリングの係数 (無効時は 1), はベクトルスケーリングの係数 (無効時は 1) である.
行列スケーリング有効時も ILU(0) 分解はスケーリング前のに対して行い, 4 行目で入力にを掛ける. したがって作用は () となり, Jacobi 前処理と異なり行列スケーリングの有無で前処理の作用が変わる. 全行でが等しい行列 (例えば中心 -6 の 7 点差分行列) でははスカラー倍であり, 線形ソルバの反復には影響しないが, の固有値はその倍率だけ変わる.
ブロックを細かくするほど並列度は上がるが, 無視する要素が増えるため前処理の効果は弱まる. GPU での選び方は「ソルバの選び方」の「前処理」に示す.