線形ソルバ
本ライブラリルーチンで用いた各反復法アルゴリズムについて紹介する. 以下では, の実行列を係数行列に持つ連立一次方程式を解くものとする. 各節では, アルゴリズムとその記号を示す. 収束判定の詳細, 破綻と非有限値の扱い, 返す値は, API リファレンスの各ソルバのsolver()の節に示す (線形ソルバに共通の扱い). は内積, は 2 ノルムである. 4 つの線形ソルバ (pcg, pbicgstab, pgmres, pcagmres) の収束判定はいずれも相対残差とset_tolerance()の値との比較 (で収束) である. 各解法が扱える行列と特徴を次に示す.
| 解法 |
クラス |
対象の行列 |
特徴 |
| 前処理付共役勾配法 |
parcel::krylov::pcg |
対称正定値 (前処理行列も対称正定値) |
1 反復あたりの演算と集団通信が少ない |
| 前処理付安定化双共役勾配法 |
parcel::krylov::pbicgstab |
対称・非対称 |
右前処理. 1 反復に SpMV と前処理を 2 回ずつ行う. 残差は単調に減るとは限らない |
| 前処理付一般化最小残差法 |
parcel::krylov::pgmres |
対称・非対称 |
右前処理. リスタート周期の中で残差ノルムを最小化する |
| 前処理付通信削減型一般化最小残差法 |
parcel::krylov::pcagmres |
対称・非対称 (モーメント法は対称・前処理なしのみ) |
右前処理. 本の基底をまとめて作って直交化し, GMRES() と同等の反復を少ない集団通信で行う. 正規直交基底を陽に作るかどうかをset_explicit_q()で選べる (作らない場合は Gram 行列の Cholesky 分解で直交化する) |
本書のアルゴリズムと数式では, 反復番号を括弧付きの上付き (, ) で, ベクトルの成分と, ベクトルの組の中の番号を下付き (, ) で表す. 括弧の無い上付きはべき乗 (), は転置, は逆行列である. 行列は大文字, ベクトルとスカラーは小文字の斜体で書き, 英語のキーワードと関数名 (, など) は立体で書く. は行列の次数 (大域の行数), は各ランクが担当する行数である. 記号は節ごとに定義し, 別の節では別の意味に使うことがある.
収束状態の定数と各ソルバでの意味は API リファレンスの「収束状態の定数と標準出力」 にまとめる.
前処理付共役勾配法[1]
共役勾配法(CG法)は対称行列向けの Krylov 部分空間法である. 係数行列と前処理行列はともに対称正定値であることを仮定する.
はsolver()の引数xに与えた初期値, はset_precon_algo()などで指定した前処理行列 (前処理の章を参照. 前処理なしでは), はset_tolerance()で指定する収束判定値 (既定 1.0e-8), はset_max_iteration()で指定する最大反復回数 (既定 10000) である. は前処理を施した残差, は探索方向, は, ・・・はスカラーである.
-
-
-
-
-
-
-
-
-
-
-
-
実装では, 11 行目のの更新を既定では毎反復行い, 探索方向は 1 本だけ持つ. 環境変数PARCEL_PSTEPに 2 以上の値を指定すると, 探索方向を本貯めて反復ごとにまとめてに反映する (のメモリの読み書きがになって少し速くなる代わりに, ベクトル本分のメモリを使う. 「メモリと速さの選択」). 解は数学的には同じで, 丸めの順序だけが変わる. 収束判定は 12 行目ので行うので, 反復回数はPARCEL_PSTEPによらない.
収束判定の詳細, 破綻と非有限値の扱い, 返す値, 実装の詳細は, API リファレンスの「収束判定と破綻の扱い」に示す.
前処理付安定化双共役勾配法[1]
安定化双共役勾配法(Bi-CGSTAB)は非対称行列向けの Krylov 部分空間法である. 前処理は右前処理として適用する. すなわちに対して反復し, 解の更新にはを掛けた方向・を用いるので, 残差は前処理を施さない残差に対応する.
はsolver()の引数xに与えた初期値, はset_precon_algo()などで指定した前処理行列, はset_tolerance() (既定 1.0e-8), はset_max_iteration() (既定 10000) の値である. は初期残差, は双対 (shadow) 残差であり, は反復中は固定して用いる. は探索方向, は中間の残差, ・・・・はスカラーである.
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
収束判定の詳細, 破綻と非有限値の扱い, 返す値, 実装の詳細は, API リファレンスの「収束判定と破綻の扱い」に示す.
前処理付一般化最小残差法[1]
一般化最小残差法(GMRES(m))は非対称行列向けの Krylov 部分空間法である. 回の Arnoldi 過程で作った部分空間の中で残差ノルムを最小化して近似解を更新し, それを初期値として反復を再開する (リスタート). PARCEL のpgmresは右前処理であり, に対して Arnoldi 過程を行い, 近似解を更新するときにだけを掛ける. そのため最小化する残差は前処理を施さない残差そのものである. Arnoldi 過程の直交化法として古典 Gram-Schmidt 法と修正 Gram-Schmidt 法が整備されている.
はsolver()の引数xに与えた初期値, は回目のリスタートの開始時の近似解, はset_precon_algo()などで指定した前処理行列, はset_restart()で指定するリスタート周期 (既定 30), はset_tolerance() (既定 1.0e-8) の値である. リスタート回数の上限はset_max_iteration()の値 (既定 10000) からと決まる (がの倍数でなければ, 最後のリスタートは端数の列で打ち切る). は正規直交基底, は Hessenberg 行列の要素, ・は Givens 回転の係数, は回転を施した右辺ベクトル, は Givens 回転後の () からなるの上三角行列, はの先頭成分である. 12〜15 行目はset_qr_algo()で修正 Gram-Schmidt 法 (parcel::qr::QR_MGS, 既定) を選んだ場合を示す. 実装はとの符号をともに反転して計算するが, 両者の反転は打ち消し合い, 結果は変わらない.
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
収束判定の詳細, 破綻と非有限値の扱い, 返す値, 実装の詳細は, API リファレンスの「収束判定と破綻の扱い」に示す.
前処理付通信削減型一般化最小残差法 [2,3]
通信削減型一般化最小残差法(CA-GMRES(s,t))は非対称行列向けの Krylov 部分空間法である. GMRES(m) の回の反復に相当する基底ベクトルをまとめて生成し, ブロック単位で直交化する. これを回繰り返して得た本の基底で近似解を更新し, それを初期解として反復を再開する. がGMRES(m)のリスタート周期に相当する. 数学的にはCA-GMRES(s,t)とGMRES(m)の収束性は同等であり, 通信削減型のQR分解を適用することでGMRES(m)よりも集団通信の回数を削減する. ただし, 一度に本の基底ベクトルを生成するため, が過大な場合には, 丸め誤差によって基底ベクトルの直交性が崩れることでGMRESよりも収束性が悪くなる. PARCELの基底は単項式基底 () のみであり, Newton 基底は実装していない. 前処理はpgmresと同じく右前処理である.
はsolver()の引数xに与えた初期値, は回目のリスタートの開始時の近似解, はset_precon_algo()などで指定した前処理行列, ・はset_restart(s, t)で指定する値 (既定, ), はset_tolerance() (既定 1.0e-8) の値である. リスタート回数の上限はset_max_iteration()の値 (既定 10000) からと決まる (がの倍数でなければ, 最後のリスタートは端数の列だけで最小二乗問題を解く). 19 行目・26 行目の QR 分解の方法はset_qr_algo()で選ぶ (parcel::qr::QR_CGS, QR_MGS (既定), QR_CHOLESKYQR. QR分解の章を参照). 以下のアルゴリズムは正規直交基底を陽に作る場合である. を作らない場合は後述する.
は単項式基底の基底変換行列 (. は第単位ベクトル), はその先頭行, はの行列要素である. 下線を付けた記号は, 付けない記号より 1 本 (1 列・1 行) 多い版を表す. は番目のブロックで生成する本の基底, はその先頭を除く本である. は正規直交化した基底であり, はその先頭列を表す. ・はの QR 分解の因子, ・はの QR 分解の因子である. はブロック古典 Gram-Schmidt 法の係数行列 (), はその先頭の列を除く列 (に対応), はの先頭列から最終行を除いたものである. は QR 分解で得るの上三角行列, はその先頭行列, ・はその第列の上成分と対角要素, はの行列要素である. はに対するの Hessenberg 行列, はその最終行を除いたものである. とは, 番目のブロックでに加わる列のうち, それぞれ前のブロックの行と番目のブロックの行の部分であり, はその最終行の要素である. は回転を施した右辺ベクトル, はその先頭成分, はの要素, ・は Givens 回転の係数である. 回転後のは上三角行列となる.
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
14〜17 行目は番目のブロックの単項式基底 (は固定) を作り, 前処理と疎行列ベクトル積だけからなる (集団通信を含まない). 35〜44 行目は個のブロックぶんの Hessenberg 行列の各列に Givens 回転を施し, 45〜47 行目で解を更新する.
収束判定の詳細, 破綻と非有限値の扱い, 返す値, 実装の詳細は, API リファレンスの「収束判定と破綻の扱い」に示す.
Q の作り方 (set_explicit_q)
pcagmresは, 直交化した基底を陽に作るかどうかをset_explicit_q(mode)で選べる (get_explicit_q()で取得できる). modeは名前空間parcel::krylovの次の定数である.
| 定数 |
値 |
動作 |
CAGMRES_Q_AUTO (既定) |
0 |
上のアルゴリズムのとおりを作る. ただしQR_CHOLESKYQRかつのときだけを作らない |
CAGMRES_Q_EXPLICIT |
1 |
常にを作る (QR_CHOLESKYQRででも作る) |
CAGMRES_Q_IMPLICIT |
2 |
どのでもを作らない (下記). QR 分解はQR_CHOLESKYQR (set_qr_algo()を呼ばなければこれを使う) またはQR_CAGMRES_CHOLESKYQR (モーメント法) |
CAGMRES_Q_IMPLICITとQR_CGS・QR_MGSの組合せ, およびQR_CAGMRES_CHOLESKYQRとCAGMRES_Q_AUTO・CAGMRES_Q_EXPLICITの組合せは, solver()の入口でstd::invalid_argumentを投げる (設定関数はどの順に呼んでもよいので, 組合せは入口で調べる). 範囲外の値はset_explicit_q()がstd::invalid_argumentを投げる. get_qr_algo()は実際に使う QR 分解を返す. 選んだ方式は計算時間の表示 (pcagmres timeの行) の末尾にQ = auto: formed, Q = implicit: not formed, CholeskyQRのように示される.
Q を作らない場合 (CAGMRES_Q_IMPLICIT) [2,3,7]
set_explicit_q(parcel::krylov::CAGMRES_Q_IMPLICIT)を指定した場合は, 上のアルゴリズムと次の 3 点が異なる.
- 正規直交基底を陽に作らない. 基底をそのまま保持し, Gram 行列の Cholesky 分解から上三角行列 () だけを求める. Hessenberg 行列は上のアルゴリズムと同じ式でから組み立て, 解の更新にはの代わりにを用いる. 既定 (
CAGMRES_Q_AUTO) のQR_CHOLESKYQRはのときだけを省略するが, CAGMRES_Q_IMPLICITはでも省略する.
- 基底を偶数番目と奇数番目に分けて格納し, それぞれの格納精度を
solver()のテンプレート引数Teven_basis・Todd_basisで選べる (既定はどちらもTbasis. CAGMRES_Q_IMPLICIT以外では使わない).
set_qr_algo(parcel::qr::QR_CAGMRES_CHOLESKYQR)を指定すると, 最初のブロックの Gram 行列をモーメントから作る (QR分解の章). が対称で前処理なしの場合に限って正しい.
はsolver()の引数xに与えた初期値, は回目のリスタートの開始時の近似解, はset_precon_algo()などで指定した前処理行列, ・はset_restart(s, t)で指定する値 (既定, ), はset_tolerance() (既定 1.0e-8) の値である. リスタート回数の上限はset_max_iteration()の値 (既定 10000) からと決まる. この節では基底の番号を 0 から数え, , はの〜行〜列の部分行列, は番目のブロックで新たに作る本の基底, は第単位ベクトル (0 始まり) である. は対称行列の Cholesky 分解の上三角行列を表す. ・は上のpcagmresのアルゴリズムと同じであり, 28〜30 行目の Givens 回転は上のアルゴリズムの 35〜44 行目と同じ計算である.
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
13 行目のはの第列であり, ブロックの始点だけをとから作る (上のアルゴリズムの 12 行目に当たる). 23 行目のはブロック古典 Gram-Schmidt 法の係数, 24 行目は射影後のの Cholesky QR であり, を上三角のまま 1 ブロックずつ延ばす. 26 行目では, は上のアルゴリズムの 21〜22 行目, は 28〜32 行目と同じ式で, , として組み立てる. 31 行目のは, 回転後のから最終行を除いた上三角行列である.
収束判定の詳細, 破綻と非有限値の扱い, 返す値, 実装の詳細は, API リファレンスの「収束判定と破綻の扱い」に示す.
直交化の精度と基底の精度
GMRES 系のソルバは Krylov 部分空間の基底を直交化しながら反復する. pgmres・pcagmresでは, 基底を格納する精度と, 直交化を計算する精度を別々に指定できる (書式は使用方法の「線形ソルバの呼び出し」).
本節では, は局所行数, はpgmresのリスタート周期 (set_restart(m)) である. とは CA-GMRES(s,t) (pcagmres) のパラメタで, set_restart(s, t)で指定する (既定, ).
- : 1 つのブロックで, 直交化せずに続けて作る基底ベクトルの本数. ブロックの先頭ベクトルから単項式基底の本を作り, この本をまとめて QR 分解する. SpMV と前処理を回続けて行う間は集団通信が無い.
- : 1 回のリスタートで作るブロックの数. 2 番目以降のブロックは, それまでのブロックの直交化済みの基底に対して直交化してから QR 分解する. 前のブロックの最後のベクトルが次のブロックの先頭になるので, 1 回のリスタートの基底は本, リスタート周期は GMRES() に相当する (線形ソルバの章).
丸め誤差があると, 直交化した基底は厳密には直交しない. 直交性の損失は, 直交化の計算に用いる精度の単位丸め誤差と, 直交化する前の基底の条件数で決まる. 修正 Gram-Schmidt 法ではに [8], 古典 Gram-Schmidt 法 [9] と Cholesky QR 法 [11] ではに比例する. は倍精度で約, 単精度で約, 半精度で約である. Cholesky QR 法は, が 1 に近づくと Gram 行列が数値的に正定値でなくなり, 分解できない. また, 直交化したを低い精度で格納すると, その丸め (の各要素に相対程度) の分だけ直交性が損なわれる.
pgmresの Arnoldi 過程は, 新しいベクトルを 1 本ずつ, それまでに直交化した基底に対して直交化する. 修正 Gram-Schmidt 法による GMRES は後退安定であり, 直交性が大きく失われるのは残差が十分小さくなってからである [10]. このため直交化の精度TGSを低精度にしても反復は進み, 影響は主に到達できる残差の下限として現れる (下限はとともに大きくなる).
pcagmresでは, 直交化は 2 段に分かれ, とがそれぞれに効く.
- ブロック内 (が効く): 単項式基底の本は直交化せずに作るので, その条件数はとともに急速に大きくなる. これを QR 分解するので, QR 分解の計算精度が直交化の成否を直接左右する. 特に Cholesky QR 法 (
pcagmresのQR_CHOLESKYQR. を作らない方式CAGMRES_Q_IMPLICITを含む) はが効くため, が大きいと低精度では分解そのものが破綻しやすい. FP16 のデータ精度・計算精度でpcagmresの Cholesky QR 系を使えないのも, この悪条件のためである (を作る方式は使える. 「低精度での既知の限界」).
- ブロック間 (が効く): 番目 () のブロックは, それまでの (本) への射影を 1 回引いてから (ブロック古典 Gram-Schmidt 法. 再直交化はしない) ブロック内の QR 分解を行う. ブロック間の直交性の損失は, 1 回の射影の計算精度と, 射影の前のブロックの条件数に依存し, ブロックを重ねる (を大きくする) ほど前のブロックとの直交性の誤差が基底に蓄積しうる.
基底の階数落ち (幸運な破綻) の判定には, から決めた閾値を用いる (Cholesky QR 法では, それ以外は).
各引数が受け持つ, 長さのベクトルを扱う計算 (内積と更新) とその精度を次に示す. pcagmresでは, 直交基底を陽に作るかどうか (set_explicit_q(). 線形ソルバの章) でTcalcQR・THessenbergの役割が異なることに注意する.
| ソルバ |
引数 |
受け持つもの |
データの大きさ |
pgmres |
Tvec (データ精度) |
基底ベクトルの格納 |
|
pgmres |
TGS |
Gram-Schmidt 直交化の内積と係数の計算 |
長さの内積 |
pgmres |
THessenberg |
最小二乗問題の解 (ホストで解く) をデバイスに渡す精度 |
長さ |
pcagmres |
Tbasis |
基底と直交化後の基底の格納 |
は, は |
pcagmres (を作る場合) |
TcalcQR |
ブロック内の QR 分解の計算 (長さの内積) |
長さの内積 |
pcagmres (を作る場合) |
THessenberg |
ブロック間の射影の計算 (長さの内積) とからの差し引き, ・射影係数・Hessenberg 行列の格納 |
長さの内積, |
pcagmres (CAGMRES_Q_IMPLICIT) |
TcalcQR |
Gram 行列の計算 (ブロック内とブロック間の長さの内積のすべて) |
長さの内積 |
pcagmres (CAGMRES_Q_IMPLICIT) |
THessenberg |
Gram 行列・・Hessenberg 行列の格納 |
程度 |
pcagmres (CAGMRES_Q_IMPLICIT) |
Todd_basis, Teven_basis |
基底の奇数番目・偶数番目の格納 |
合わせて |
サンプルがTcalcQR・THessenbergを倍精度に固定する理由は次のとおりである. 精度を下げてメモリ量とデータ移動量が減るのは, 長さのベクトルを本以上持つ基底 (Tbasis) である. 一方, 直交化の成否を決めるのは, ブロック内とブロック間の直交化の計算精度 (pcagmresではTcalcQRとTHessenberg, を作らない方式CAGMRES_Q_IMPLICITではTcalcQR) である. これらは基底を読みながら内積を累積する精度であり, 上げても読み書きする基底のデータの量は変わらない. 格納する行列 (・Hessenberg 行列など) は程度と小さい. このため, 基底だけをデータ精度に合わせて下げ, 直交化の計算と小さな行列は倍精度に保つという使い分けになる. このとき直交性は, 基底を格納するTbasisの丸めで決まる程度まで保たれる. C言語・Fortran のラッパ (capi/wrapper_parcel_sycl.cpp) はこの 2 つをマクロparcel_solver_calc_qr_type (既定parcel_double) で与え, 検証用サンプルtests/verify/parcel_krylov_sample_verify.cppはparcel_doubleに固定している. pgmresのTGS・THessenbergは, どちらもデータ精度を与えている (ライブラリの既定はparcel_double). 「精度構成」の「代表的な 13 の構成」はいずれもpcagmres (を作らない方式を含む) のTcalcQR・THessenbergを倍精度とする. これらを下げた場合の収束は確かめていない.