9 固有値ソルバ
本ライブラリルーチンで用いた固有値解法について紹介する. 対象は CRS 形式で与えたの実係数疎行列の標準固有値問題 であり, 一般化固有値問題 は扱わない. 各解法が扱える行列と返す固有値を次に示す. 記号の約束は線形ソルバの章の冒頭に示したとおりである.
| 解法 | クラス | 対象の行列 | 返す固有値 |
|---|---|---|---|
| べき乗法 | parcel::krylov::power |
対称・非対称 | 絶対値最大の固有値 1 個 (実数) |
| 逆べき乗法 | parcel::krylov::inverse_power |
対称・非対称. 内部の線形ソルバにpcgを選んだ場合は対称 (正定値または負定値) |
絶対値最小の固有値 1 個 (実数) |
| Krylov-Schur 法 | parcel::krylov::ks_arnoldi |
対称・非対称 | 絶対値の大きい (shift-invert 時はシフトに近い) 複数の固有値. 複素共役対を含む (実部・虚部の組で返す) |
べき乗法と逆べき乗法は実数の Rayleigh 商で固有値を推定するため, 求める側の端 (絶対値最大または最小) の固有値が複素共役対である場合や, 絶対値の等しい固有値が複数ある場合 (例: ) には収束しない. そのような行列には Krylov-Schur 法を用いる. 前処理の扱い (set_precon_spectrum()) は各節に示す. set_precon_spectrum(true)でべき乗法 (絶対値最大側) と逆べき乗法 (絶対値最小側) を用いると, 前処理後の行列の固有値分布と条件数を両端から評価できる.
9.1 べき乗法 [4]
べき乗法は絶対値最大の固有値とそれに対応する固有ベクトルを求める最も基本的な反復法である. の対称性は仮定しない. 反復で掛ける作用素は, set_precon_spectrum()で次のように選ぶ.
| モード | 指定方法 | 返す固有値 | |
|---|---|---|---|
set_precon_spectrum(false) (既定) |
の絶対値最大の固有値 | ||
set_precon_spectrum(true) |
の絶対値最大の固有値 |
のモードでは, 各反復でを掛けてからを掛ける. は, 利用者がset_precon_algo()・set_blockjacobi()・set_jacobi()・set_scaling_matrix()・set_scaling_vector()で指定した設定 (前処理の章を参照) に従い, ソルバに渡したから作る. のモードでは, これらの前処理の設定は指定しても使わない. 前処理はスペクトルを圧縮するため, の固有値は 1 付近に密集しやすい. このとき絶対値最大の固有値と 2 番目の固有値の比が 1 に近づき, 収束が遅くなる, あるいは収束しなくなる (Krylov-Schur 法も同じ).
- アルゴリズム
は大域行番号から で作る初期ベクトルである (EigenVecの入力値は使わない). 全要素 1 のベクトルは特定の固有ベクトルと厳密に直交することがあるため用いない. 各ランクの先頭の大域行番号は局所行数の累積和 (MPI_Exscan) で求めるので, は MPI の分割数や不均等な行分割によらない. はset_precon_spectrum()の指定値, は前処理行列, はset_tolerance()で指定する収束判定値 (既定 1.0e-8), はset_max_iteration()で指定する最大反復回数 (既定 10000) である.
収束の速さは絶対値最大の固有値と 2 番目に絶対値の大きい固有値の比で決まり, その比が 1 に近いほど遅い.
収束判定の詳細, 破綻と非有限値の扱い, 返す値, 実装の詳細は, API リファレンスの「収束判定と破綻の扱い」に示す.
9.2 逆べき乗法 [4]
逆べき乗法は絶対値最小の固有値とそれに対応する固有ベクトルを求める. は陽に作らず, 各反復で連立一次方程式を内部の線形ソルバで解く. よりであるから, はにおけるの Rayleigh 商であり, が絶対値最小の固有値の固有ベクトルに収束するにつれてはその固有値に収束する.
内部の線形ソルバの既定は右前処理付き一般化最小残差法 (parcel::krylov::pgmres. 直交化は修正 Gram-Schmidt 法) であり, の対称性は要らない. ただし絶対値最小の固有値が複素共役対の場合は Rayleigh 商が収束しないので, Krylov-Schur 法の shift-invert をで用いる. set_linsolve_algo(parcel::krylov::LINSOLVE_PCG)を指定すると, 内部の線形ソルバを前処理付き共役勾配法 (parcel::krylov::pcg) に替える. このときは対称 (正定値または負定値) でなければならない. pcgを選べるのはのモードだけであり, のモードでは指定によらずpgmresを用いる.
反復で作用させるは, set_precon_spectrum()で次のように選ぶ. は陽に作らず, 内部の線形ソルバで方程式を解いて作用させる.
| モード | 指定方法 | 返す固有値 | |
|---|---|---|---|
set_precon_spectrum(false) (既定) |
の絶対値最小の固有値 | ||
set_precon_spectrum(true) |
の絶対値最小の固有値 |
のモードでは, 内部の線形ソルバでを解く. その前処理はset_linsolve_precon_algo()などの設定でから作る (既定は Jacobi 前処理PRECON_JACOBI, 反復 1 回). 前処理を低精度にした構成では, set_linsolve_precon_algo(parcel::PRECON_NONE)とした方が速い場合がある (「低精度での既知の限界」). のモードでは, 内部の右前処理pgmres (前処理は) でを解き, をそのまま用いる.
内部の線形ソルバは, 外側の固有値反復とは別の設定を持つ. 種類はset_linsolve_algo(), 収束判定値はset_linsolve_tolerance(), 最大反復回数はset_linsolve_max_iteration(), pgmresのリスタート周期はset_linsolve_restart(), 前処理はset_linsolve_precon_algo()・set_linsolve_blockjacobi()・set_linsolve_jacobi()で指定する (Krylov-Schur 法の shift-invert と共通. 一覧と既定値は API リファレンスの「固有値ソルバ共通のメンバ関数」). のモードでは内部pgmresの前処理はそのものであり, set_linsolve_precon_algo()などの指定は使わない. はべき乗法と同じく利用者の前処理の設定でから作る.
のモードでを陽に作る必要はなく, 前処理はの作用だけで足りる. 右前処理 GMRES は内部でを係数行列として扱っており, 最後にを掛けずに内部変数を返せばの作用が得られるためである.
- アルゴリズム
はべき乗法と同じ式で作り, 正規化してから用いる. はset_precon_spectrum()の指定値, は前処理行列, は内部の線形ソルバの前処理行列 (前処理なしでは), はset_linsolve_restart()で指定するリスタート周期 (既定 30), はset_tolerance() (既定 1.0e-8), はset_max_iteration() (既定 10000) の値である. 4 行目と 6 行目の内部の線形ソルバは初期値をとし, 相対残差がset_linsolve_tolerance()の値 (既定 1.0e-10) を下回るまで, 最大set_linsolve_max_iteration()の値 (既定 5000) まで反復する. 6 行目は既定では GMRES(m), set_linsolve_algo(parcel::krylov::LINSOLVE_PCG)の指定時は CG である.
収束判定の詳細, 破綻と非有限値の扱い, 返す値, 実装の詳細は, API リファレンスの「収束判定と破綻の扱い」に示す.
9.3 Krylov-Schur 法 [5]
ks_arnoldiは Krylov-Schur 法 [5] を実装したもので, Arnoldi 分解と実 Schur 分解によるリスタートを組み合わせて複数の固有対を同時に求める. 対称行列・非対称行列のいずれにも適用でき, 複素共役対の固有値も求まる. Arnoldi 分解で用いる作用素は次のとおりである.
| モード | 指定方法 | 返す固有値 | |
|---|---|---|---|
| シフトなし | set_precon_spectrum(false) (既定) |
(の固有値) | |
| シフトなし () | set_precon_spectrum(true) |
(の固有値) | |
| shift-invert | set_shift(σ) + 第 4 引数にを渡す |
(の固有値) | |
| shift-invert (第 4 引数なし) | set_shift(σ)のみ |
(の固有値) | |
| shift-invert () | set_shift(σ) + set_precon_spectrum(true) |
(の固有値) |
はべき乗法と同じく利用者の前処理の設定でから作り, シフトなしののモードでは使わない. shift-invert では, 各 Arnoldi ステップで内部のpgmresにより (または) を解く. 内部の線形ソルバの設定は逆べき乗法と同じset_linsolve_*で指定する. を第 4 引数で渡した場合は, 内部pgmresの前処理をこの行列から作る (既定は Jacobi 前処理). 第 4 引数を省いた場合はとシフトから解き, に固定する. のモードでは内部pgmresの前処理はであり, は不要である.
- アルゴリズム
は利用者がEigenVecの先頭要素に与える初期ベクトル, は上の表の作用素, , はを要素に持つ行列, は部分空間の最大次元, はリスタートで保持する Ritz ベクトル数, は収束を判定する固有値の数, は最大リスタート回数である. ・・はset_ks_subspace(m, k_keep, nev) (既定 30, 10, 4) で, はset_ks_max_restart() (既定 200) で, はset_tolerance() (既定 1.0e-8) で指定する. は第単位ベクトルである.
7〜11 行目の直交化は, 既定では古典 Gram-Schmidt 法を 2 回適用する CGS2 である (1 回の射影の内積をまとめて集団通信 1 回で集め, 基底の更新を 1 回の gemv で行う). set_qr_algo(parcel::qr::QR_MGS)を呼ぶと, 修正 Gram-Schmidt 法を 2 回適用する (列ごとに内積と axpy を行う) 方法に替わる (QR_CGSが CGS2. pgmresと同じ定数で, ks_arnoldiではどちらも 2 回適用する. それ以外の値はstd::invalid_argument). どちらも 2 回目で直交性を回復し, 固有値の精度は同等である. 1 ランクの局所行数が小さい CPU の構成では修正 Gram-Schmidt 法が速い場合があり, 局所行数が大きい CPU と GPU では CGS2 が速い. 既定は CGS2 である. ただし PS-A 向けのビルド (spack の環境psa) は MGS2 が既定である (ビルド時のマクロPARCEL_KS_ORTHO_DEFAULT=mgs, spack のバリアントks_ortho=mgs. 「ks_arnoldi の直交化の既定」). 1 スレッドあたりの局所行数が小さく大きなキャッシュを持つ CPU では MGS2 が速いことがあるためである. set_qr_algo()で指定した値はビルド時の既定より優先する.
27 行目の固有ベクトルは, EigenVecに入る本数 (本) だけ書く. 上位本だけが要る場合は, EigenVecを要素で確保すればよい.
収束判定の詳細, 破綻と非有限値の扱い, 返す値, 実装の詳細は, API リファレンスの「収束判定と破綻の扱い」に示す.