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

9 固有値ソルバ

 本ライブラリルーチンで用いた固有値解法について紹介する. 対象は CRS 形式で与えたnglobal×nglobaln_{global} \times n_{global}の実係数疎行列AAの標準固有値問題 Ax=λxAx = \lambda x であり, 一般化固有値問題 Ax=λBxAx = \lambda Bx は扱わない. 各解法が扱える行列と返す固有値を次に示す. 記号の約束は線形ソルバの章の冒頭に示したとおりである.

解法 クラス 対象の行列 返す固有値
べき乗法 parcel::krylov::power 対称・非対称 絶対値最大の固有値 1 個 (実数)
逆べき乗法 parcel::krylov::inverse_power 対称・非対称. 内部の線形ソルバにpcgを選んだ場合は対称 (正定値または負定値) 絶対値最小の固有値 1 個 (実数)
Krylov-Schur 法 parcel::krylov::ks_arnoldi 対称・非対称 絶対値の大きい (shift-invert 時はシフトσ\sigmaに近い) 複数の固有値. 複素共役対を含む (実部・虚部の組で返す)

 べき乗法と逆べき乗法は実数の Rayleigh 商で固有値を推定するため, 求める側の端 (絶対値最大または最小) の固有値が複素共役対である場合や, 絶対値の等しい固有値が複数ある場合 (例: ±λ\pm\lambda) には収束しない. そのような行列には Krylov-Schur 法を用いる. 前処理の扱い (set_precon_spectrum()) は各節に示す. set_precon_spectrum(true)でべき乗法 (絶対値最大側) と逆べき乗法 (絶対値最小側) を用いると, 前処理後の行列AK−1AK^{-1}の固有値分布と条件数を両端から評価できる.


9.1 べき乗法 [4]

 べき乗法は絶対値最大の固有値とそれに対応する固有ベクトルを求める最も基本的な反復法である. AAの対称性は仮定しない. 反復で掛ける作用素Op\mathrm{Op}は, set_precon_spectrum()で次のように選ぶ.

モード 指定方法 Op\mathrm{Op} 返す固有値
AA set_precon_spectrum(false) (既定) AA AAの絶対値最大の固有値
AK−1AK^{-1} set_precon_spectrum(true) AK−1AK^{-1} AK−1AK^{-1}の絶対値最大の固有値

 AK−1AK^{-1}のモードでは, 各反復でK−1K^{-1}を掛けてからAAを掛ける. KKは, 利用者がset_precon_algo()・set_blockjacobi()・set_jacobi()・set_scaling_matrix()・set_scaling_vector()で指定した設定 (前処理の章を参照) に従い, ソルバに渡したAAから作る. AAのモードでは, これらの前処理の設定は指定しても使わない. 前処理はスペクトルを圧縮するため, AK−1AK^{-1}の固有値は 1 付近に密集しやすい. このとき絶対値最大の固有値と 2 番目の固有値の比が 1 に近づき, 収束が遅くなる, あるいは収束しなくなる (Krylov-Schur 法も同じ).

 x(0)x^{(0)}は大域行番号ggから 1+0.5sin⁡(0.317g+0.7)+0.3cos⁡(0.181g−1.3)1 + 0.5\sin(0.317g + 0.7) + 0.3\cos(0.181g - 1.3) で作る初期ベクトルである (EigenVecの入力値は使わない). 全要素 1 のベクトルは特定の固有ベクトルと厳密に直交することがあるため用いない. 各ランクの先頭の大域行番号は局所行数の累積和 (MPI_Exscan) で求めるので, x(0)x^{(0)}は MPI の分割数や不均等な行分割によらない. specspecはset_precon_spectrum()の指定値, KKは前処理行列, toltolはset_tolerance()で指定する収束判定値 (既定 1.0e-8), NNはset_max_iteration()で指定する最大反復回数 (既定 10000) である.

  1. Chooseinitialguessx(0)\mathrm{Choose}\ \mathrm{initial}\ \mathrm{guess}\ x^{(0)}
  2. fori=0,1,…,N−1\mathrm{for}\ i = 0,1,\ldots,N - 1
  3.   ifspecthen\mathrm{if}\ spec\ \mathrm{then}
  4.     solvezfromKz=x(i)\mathrm{solve}\ z\ \mathrm{from}\ Kz = x^{(i)}
  5.   else\mathrm{else}
  6.     z=x(i)z = x^{(i)}
  7.   endif\mathrm{endif}
  8.   y=Azy = Az
  9.   λ(i)=⟨x(i),y⟩/⟨x(i),x(i)⟩\lambda^{(i)} = \langle x^{(i)},y \rangle\ /\ \langle x^{(i)},x^{(i)} \rangle
  10.   x(i+1)=y/∥y∥x^{(i + 1)} = y\ /\ \|y\|
  11.   ifi>0and|λ(i)−λ(i−1)|/|λ(i)|<tolthen\mathrm{if}\ i > 0\ \mathrm{and}\ |\lambda^{(i)} - \lambda^{(i - 1)}|\ /\ |\lambda^{(i)}| < tol\ \mathrm{then}
  12.     quit\mathrm{quit}
  13.   endif\mathrm{endif}
  14. end\mathrm{end}

 収束の速さは絶対値最大の固有値と 2 番目に絶対値の大きい固有値の比で決まり, その比が 1 に近いほど遅い.

 収束判定の詳細, 破綻と非有限値の扱い, 返す値, 実装の詳細は, API リファレンスの「収束判定と破綻の扱い」に示す.


9.2 逆べき乗法 [4]

 逆べき乗法は絶対値最小の固有値とそれに対応する固有ベクトルを求める. A−1A^{-1}は陽に作らず, 各反復で連立一次方程式Ay=x(i)Ay = x^{(i)}を内部の線形ソルバで解く. y=A−1x(i)y = A^{-1}x^{(i)}よりx(i)=Ayx^{(i)} = Ayであるから, θ(i)=⟨y,x(i)⟩/⟨y,y⟩=⟨y,Ay⟩/⟨y,y⟩\theta^{(i)} = \langle y, x^{(i)} \rangle / \langle y, y \rangle = \langle y, Ay \rangle / \langle y, y \rangleはyyにおけるAAの Rayleigh 商であり, yyが絶対値最小の固有値の固有ベクトルに収束するにつれてθ(i)\theta^{(i)}はその固有値に収束する.

 内部の線形ソルバの既定は右前処理付き一般化最小残差法 (parcel::krylov::pgmres. 直交化は修正 Gram-Schmidt 法) であり, AAの対称性は要らない. ただし絶対値最小の固有値が複素共役対の場合は Rayleigh 商が収束しないので, Krylov-Schur 法の shift-invert をσ=0\sigma = 0で用いる. set_linsolve_algo(parcel::krylov::LINSOLVE_PCG)を指定すると, 内部の線形ソルバを前処理付き共役勾配法 (parcel::krylov::pcg) に替える. このときAAは対称 (正定値または負定値) でなければならない. pcgを選べるのはAAのモードだけであり, AK−1AK^{-1}のモードでは指定によらずpgmresを用いる.

 反復で作用させるOp\mathrm{Op}は, set_precon_spectrum()で次のように選ぶ. Op\mathrm{Op}は陽に作らず, 内部の線形ソルバで方程式を解いて作用させる.

モード 指定方法 Op\mathrm{Op} 返す固有値
AA set_precon_spectrum(false) (既定) A−1A^{-1} AAの絶対値最小の固有値
AK−1AK^{-1} set_precon_spectrum(true) (AK−1)−1(AK^{-1})^{-1} AK−1AK^{-1}の絶対値最小の固有値

 AAのモードでは, 内部の線形ソルバでAy=x(i)Ay = x^{(i)}を解く. その前処理KinK_{in}はset_linsolve_precon_algo()などの設定でAAから作る (既定は Jacobi 前処理PRECON_JACOBI, 反復 1 回). 前処理を低精度にした構成では, set_linsolve_precon_algo(parcel::PRECON_NONE)とした方が速い場合がある (「低精度での既知の限界」). AK−1AK^{-1}のモードでは, 内部の右前処理pgmres (前処理はKK) で(AK−1)y=x(i)(AK^{-1})y = x^{(i)}を解き, yyをそのまま用いる.

 内部の線形ソルバは, 外側の固有値反復とは別の設定を持つ. 種類はset_linsolve_algo(), 収束判定値はset_linsolve_tolerance(), 最大反復回数はset_linsolve_max_iteration(), pgmresのリスタート周期はset_linsolve_restart(), 前処理KinK_{in}はset_linsolve_precon_algo()・set_linsolve_blockjacobi()・set_linsolve_jacobi()で指定する (Krylov-Schur 法の shift-invert と共通. 一覧と既定値は API リファレンスの「固有値ソルバ共通のメンバ関数」). AK−1AK^{-1}のモードでは内部pgmresの前処理はKKそのものであり, set_linsolve_precon_algo()などの指定は使わない. KKはべき乗法と同じく利用者の前処理の設定でAAから作る.

 AK−1AK^{-1}のモードでKKを陽に作る必要はなく, 前処理はK−1K^{-1}の作用だけで足りる. 右前処理 GMRES は内部でAK−1AK^{-1}を係数行列として扱っており, 最後にK−1K^{-1}を掛けずに内部変数yyを返せば(AK−1)−1(AK^{-1})^{-1}の作用が得られるためである.

 x(0)x^{(0)}はべき乗法と同じ式で作り, 正規化してから用いる. specspecはset_precon_spectrum()の指定値, KKは前処理行列, KinK_{in}は内部の線形ソルバの前処理行列 (前処理なしではKin=IK_{in} = I), mmはset_linsolve_restart()で指定するリスタート周期 (既定 30), toltolはset_tolerance() (既定 1.0e-8), NNはset_max_iteration() (既定 10000) の値である. 4 行目と 6 行目の内部の線形ソルバは初期値をy=0y = 0とし, 相対残差がset_linsolve_tolerance()の値 (既定 1.0e-10) を下回るまで, 最大set_linsolve_max_iteration()の値 (既定 5000) まで反復する. 6 行目は既定では GMRES(m), set_linsolve_algo(parcel::krylov::LINSOLVE_PCG)の指定時は CG である.

  1. Chooseinitialguessx(0)with∥x(0)∥=1\mathrm{Choose}\ \mathrm{initial}\ \mathrm{guess}\ x^{(0)}\ \mathrm{with}\ \|x^{(0)}\| = 1
  2. fori=0,1,…,N−1\mathrm{for}\ i = 0,1,\ldots,N - 1
  3.   ifspecthen\mathrm{if}\ spec\ \mathrm{then}
  4.     solveyfrom(AK−1)y=x(i)byGMRES(m)preconditionedwithK\mathrm{solve}\ y\ \mathrm{from}\ (AK^{-1})y = x^{(i)}\ \mathrm{by}\ \mathrm{GMRES}(m)\ \mathrm{preconditioned}\ \mathrm{with}\ K
  5.   else\mathrm{else}
  6.     solveyfromAy=x(i)byGMRES(m)orCGpreconditionedwithKin\mathrm{solve}\ y\ \mathrm{from}\ Ay = x^{(i)}\ \mathrm{by}\ \mathrm{GMRES}(m)\ \mathrm{or}\ \mathrm{CG}\ \mathrm{preconditioned}\ \mathrm{with}\ K_{in}
  7.   endif\mathrm{endif}
  8.   θ(i)=⟨y,x(i)⟩/⟨y,y⟩\theta^{(i)} = \langle y,x^{(i)} \rangle\ /\ \langle y,y \rangle
  9.   x(i+1)=y/∥y∥x^{(i + 1)} = y\ /\ \|y\|
  10.   ifi>0and|θ(i)−θ(i−1)|/|θ(i)|<tolthen\mathrm{if}\ i > 0\ \mathrm{and}\ |\theta^{(i)} - \theta^{(i - 1)}|\ /\ |\theta^{(i)}| < tol\ \mathrm{then}
  11.     quit\mathrm{quit}
  12.   endif\mathrm{endif}
  13. end\mathrm{end}

 収束判定の詳細, 破綻と非有限値の扱い, 返す値, 実装の詳細は, API リファレンスの「収束判定と破綻の扱い」に示す.


9.3 Krylov-Schur 法 [5]

 ks_arnoldiは Krylov-Schur 法 [5] を実装したもので, Arnoldi 分解と実 Schur 分解によるリスタートを組み合わせて複数の固有対を同時に求める. 対称行列・非対称行列のいずれにも適用でき, 複素共役対の固有値も求まる. Arnoldi 分解で用いる作用素Op\mathrm{Op}は次のとおりである.

モード 指定方法 Op\mathrm{Op} 返す固有値
シフトなし set_precon_spectrum(false) (既定) AA λ=θ\lambda = \theta (AAの固有値)
シフトなし (AK−1AK^{-1}) set_precon_spectrum(true) AK−1AK^{-1} λ=θ\lambda = \theta (AK−1AK^{-1}の固有値)
shift-invert set_shift(σ) + 第 4 引数にA−σIA - \sigma Iを渡す (A−σI)−1(A - \sigma I)^{-1} λ=σ+1/θ\lambda = \sigma + 1/\theta (AAの固有値)
shift-invert (第 4 引数なし) set_shift(σ)のみ (A−σI)−1(A - \sigma I)^{-1} λ=σ+1/θ\lambda = \sigma + 1/\theta (AAの固有値)
shift-invert (AK−1AK^{-1}) set_shift(σ) + set_precon_spectrum(true) (AK−1−σI)−1(AK^{-1} - \sigma I)^{-1} λ=σ+1/θ\lambda = \sigma + 1/\theta (AK−1AK^{-1}の固有値)

 KKはべき乗法と同じく利用者の前処理の設定でAAから作り, シフトなしのAAのモードでは使わない. shift-invert では, 各 Arnoldi ステップで内部のpgmresにより(A−σI)z=v(A - \sigma I)z = v (または(AK−1−σI)z=v(AK^{-1} - \sigma I)z = v) を解く. 内部の線形ソルバの設定は逆べき乗法と同じset_linsolve_*で指定する. A−σIA - \sigma Iを第 4 引数で渡した場合は, 内部pgmresの前処理KinK_{in}をこの行列から作る (既定は Jacobi 前処理). 第 4 引数を省いた場合はAAとシフトσ\sigmaから解き, Kin=IK_{in} = Iに固定する. AK−1AK^{-1}のモードでは内部pgmresの前処理はKKであり, A−σIA - \sigma Iは不要である.

 x(0)x^{(0)}は利用者がEigenVecの先頭nlocaln_{local}要素に与える初期ベクトル, Op\mathrm{Op}は上の表の作用素, Vj=[v1,…,vj]V_{j} = [v_{1},\ldots,v_{j}], HHはhi,jh_{i,j}を要素に持つ行列, mmは部分空間の最大次元, kkeepk_{keep}はリスタートで保持する Ritz ベクトル数, nevnevは収束を判定する固有値の数, NRN_{R}は最大リスタート回数である. mm・kkeepk_{keep}・nevnevはset_ks_subspace(m, k_keep, nev) (既定 30, 10, 4) で, NRN_{R}はset_ks_max_restart() (既定 200) で, toltolはset_tolerance() (既定 1.0e-8) で指定する. eme_{m}は第mm単位ベクトルである.

  1. Computev1=x(0)/∥x(0)∥forsomeinitialguessx(0)\mathrm{Compute}\ v_{1} = x^{(0)}\ /\ \|x^{(0)}\|\ \mathrm{for}\ \mathrm{some}\ \mathrm{initial}\ \mathrm{guess}\ x^{(0)}
  2. k=0k = 0
  3. forν=0,1,…,NR−1\mathrm{for}\ \nu = 0,1,\ldots,N_{R} - 1
  4.   forj=k+1,…,m\mathrm{for}\ j = k + 1,\ldots,m
  5.     w=Opvjw = \mathrm{Op}\ v_{j}
  6.     h1:j,j=0h_{1:j,j} = 0
  7.     forpass=1,2\mathrm{for}\ pass = 1,2
  8.       ξ=VjTw\xi = V_{j}^{T}w
  9.       w=w−Vjξw = w - V_{j}\xi
  10.       h1:j,j=h1:j,j+ξh_{1:j,j} = h_{1:j,j} + \xi
  11.     end\mathrm{end}
  12.     hj+1,j=∥w∥h_{j + 1,j} = \|w\|
  13.     vj+1=w/hj+1,jv_{j + 1} = w\ /\ h_{j + 1,j}
  14.   end\mathrm{end}
  15.   Computeeigenpairs(θl,yl)ofHmandsortby|θl|indescendingorder\mathrm{Compute}\ \mathrm{eigenpairs}\ (\theta_{l},y_{l})\ \mathrm{of}\ H_{m}\ \mathrm{and}\ \mathrm{sort}\ \mathrm{by}\ |\theta_{l}|\ \mathrm{in}\ \mathrm{descending}\ \mathrm{order}
  16.   if|hm+1,m||emTyl|/|θl|≤tolforl=1,…,nevthen\mathrm{if}\ |h_{m + 1,m}||e_{m}^{T}y_{l}|\ /\ |\theta_{l}| \leq tol\ \mathrm{for}\ l = 1,\ldots,nev\ \mathrm{then}
  17.     quit\mathrm{quit}
  18.   endif\mathrm{endif}
  19.   ComputerealSchurformHm=QTQT\mathrm{Compute}\ \mathrm{real}\ \mathrm{Schur}\ \mathrm{form}\ H_{m} = QTQ^{T}
  20.   ReorderQ,Tsothatthekkeeplargest|θ|comefirstandsetk\mathrm{Reorder}\ Q,T\ \mathrm{so}\ \mathrm{that}\ \mathrm{the}\ k_{keep}\ \mathrm{largest}\ |\theta|\ \mathrm{come}\ \mathrm{first}\ \mathrm{and}\ \mathrm{set}\ k
  21.   Vk=VmQ:,1:kV_{k} = V_{m}Q_{:,1:k}
  22.   vk+1=vm+1v_{k + 1} = v_{m + 1}
  23.   H1:k,1:k=T1:k,1:k,hk+1,1:k=hm+1,mQm,1:kH_{1:k,1:k} = T_{1:k,1:k},\ \ h_{k + 1,1:k} = h_{m + 1,m}Q_{m,1:k}
  24. end\mathrm{end}
  25. Computeeigenpairs(θl,yl)ofHmandsortby|θl|indescendingorder\mathrm{Compute}\ \mathrm{eigenpairs}\ (\theta_{l},y_{l})\ \mathrm{of}\ H_{m}\ \mathrm{and}\ \mathrm{sort}\ \mathrm{by}\ |\theta_{l}|\ \mathrm{in}\ \mathrm{descending}\ \mathrm{order}
  26. forl=1,…,kkeep\mathrm{for}\ l = 1,\ldots,k_{keep}
  27.   xl=Vmylx_{l} = V_{m}y_{l}
  28.   ifshiftinvertmodethen\mathrm{if}\ \mathrm{shift}\ \mathrm{invert}\ \mathrm{mode}\ \mathrm{then}
  29.     λl=σ+1/θl\lambda_{l} = \sigma + 1\ /\ \theta_{l}
  30.   else\mathrm{else}
  31.     λl=θl\lambda_{l} = \theta_{l}
  32.   endif\mathrm{endif}
  33. end\mathrm{end}

 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に入る本数 (min⁡(kkeep,要素数/nlocal)\min(k_{keep}, \text{要素数}/n_{local})本) だけ書く. 上位nevnev本だけが要る場合は, EigenVecをnlocal×nevn_{local} \times nev要素で確保すればよい.

 収束判定の詳細, 破綻と非有限値の扱い, 返す値, 実装の詳細は, API リファレンスの「収束判定と破綻の扱い」に示す.