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

2 ソルバごとの収束判定

 ソルバごとに, 収束判定の方法と, 破綻・非有限値に出会ったときの収束状態と返す値を示す. 言語によらない. 表の「解」「反復回数」「残差」は結果の値であり, NNは最大反復回数である. 方法の全体は利用者ガイドの線形ソルバの章と固有値ソルバの章に示す.

2.1 pcg

 反復ii (i=0,1,…i = 0, 1, \ldots) ごとに, 探索方向p(i)p^{(i)}とステップ幅α(i)\alpha^{(i)}で解をx(i+1)=x(i)+α(i)p(i)x^{(i+1)} = x^{(i)} + \alpha^{(i)}p^{(i)}, 残差を漸化式r(i+1)=r(i)−α(i)Ap(i)r^{(i+1)} = r^{(i)} - \alpha^{(i)}Ap^{(i)}で更新した直後に, 漸化式の相対残差∥r(i+1)∥/∥b∥\|r^{(i+1)}\| / \|b\|を調べる (方法の全体は利用者ガイドのアルゴリズム). 判定に用いるのは漸化式の残差であり, 真の残差b−Ax(i+1)b - Ax^{(i+1)}ではない. 反復の前に初期残差r(0)=b−Ax(0)r^{(0)} = b - Ax^{(0)}の相対残差を調べ, toltol未満なら反復しない. 結果は次のとおりである (上の行から順に調べる).

条件 収束状態 解 反復回数 残差
反復の前に初期残差の相対残差 <tol< tol CONVERGED_RTOL 初期値 (変えない) 0 初期残差の相対残差 (真の残差も同じ値)
相対残差が非有限 (NaN / Inf) DIVERGED_NANORINF その反復のx(i+1)x^{(i+1)} i+1i + 1 その非有限値
相対残差 <tol< tol CONVERGED_RTOL x(i+1)x^{(i+1)} i+1i + 1 その相対残差
NN回の反復で上に当たらない DIVERGED_ITS x(N)x^{(N)} NN 最後の相対残差

 ∥b∥=0\|b\| = 0の場合は線形ソルバに共通の扱いによる. ゼロ割りなどの破綻は検出しないので DIVERGED_BREAKDOWN にはならず, その結果残差が非有限になれば DIVERGED_NANORINF となる. rank 0 は反復ごとに反復回数 : residual norm = ...の行を書く. 真の相対残差∥b−Ax∥/∥b∥\|b - Ax\| / \|b\|は終了後に計算してfinish : residual true normの行に書き, 真の残差として返すだけで, 判定には用いない.

 解の更新は環境変数PARCEL_PSTEP (既定 1) 反復ぶんをまとめて行い, 終了時 (どの条件で終えた場合も) に残りを加えるので, 返すxxは上の表のとおりである. 既定の 1 では探索方向を 1 本だけ持つ. PARCEL_PSTEP=4では探索方向の履歴 4 本を持ち (ベクトル 3 本分のメモリを使う), 解の読み書きが減って少し速くなる (利用者ガイドの「メモリと速さの選択」). PARCEL_PSTEPを 2 以上にすると, 反復途中のxxは最大PARCEL_PSTEP反復ぶん遅れる (利用者ガイドの「漸化式の残差と真の残差」).

2.2 pbicgstab

 反復ii (i=0,1,…i = 0, 1, \ldots) では, 探索方向p(i)p^{(i)}からp̂=K−1p(i)\hat{p} = K^{-1}p^{(i)}, q=Ap̂q = A\hat{p}, α=ρ(i)/⟨r*,q⟩\alpha = \rho^{(i)} / \langle r^{\ast},q \rangle (r*r^{\ast}は初期残差r(0)r^{(0)}に固定した双対残差, ρ(i)=⟨r*,r(i)⟩\rho^{(i)} = \langle r^{\ast},r^{(i)} \rangle), 中間の残差e=r(i)−αqe = r^{(i)} - \alpha q, ê=K−1e\hat{e} = K^{-1}e, v=Aêv = A\hat{e}, ω=⟨e,v⟩/⟨v,v⟩\omega = \langle e,v \rangle / \langle v,v \rangleを求め, 解をx(i+1)=x(i)+αp̂+ωêx^{(i+1)} = x^{(i)} + \alpha\hat{p} + \omega\hat{e}, 残差を漸化式r(i+1)=e−ωvr^{(i+1)} = e - \omega vで更新する (方法の全体は利用者ガイドのアルゴリズム. ω\omegaは利用者ガイドのc3c_{3}, ρ\rhoはc1c_{1}). 収束判定には pcg と同じく更新直後の漸化式の相対残差∥r(i+1)∥/∥b∥\|r^{(i+1)}\| / \|b\|を用いる. 反復の前に初期残差の相対残差がtoltol未満なら, pcg と同じく反復せずに CONVERGED_RTOL (反復回数 0, 解は初期値のまま, 残差・真の残差は初期残差の相対残差) を返す. 破綻はα\alpha, ω\omega, 次の探索方向の係数β=ρ(i+1)/(⟨r*,q⟩ω)\beta = \rho^{(i+1)} / (\langle r^{\ast},q \rangle\omega)をそれぞれ作る前に調べる. 結果は次のとおりである (反復の中で上の行から順に調べる).

調べる時点 条件 収束状態 解 反復回数 残差
α\alphaを作る前 ⟨r*,q⟩\langle r^{\ast},q \rangleが 0 または非有限 DIVERGED_BREAKDOWN その反復の開始時のx(i)x^{(i)} ii 前の反復の相対残差 (1 反復目では初期残差の相対残差)
ω\omegaを作る前 v=0v = 0 (⟨v,v⟩=0\langle v,v \rangle = 0) で∥e∥/∥b∥\|e\|/\|b\|が非有限 DIVERGED_NANORINF x(i)+αp̂x^{(i)} + \alpha\hat{p} i+1i + 1 ∥e∥/∥b∥\|e\|/\|b\|
同上 v=0v = 0 で∥e∥/∥b∥<tol\|e\|/\|b\| < tol CONVERGED_RTOL x(i)+αp̂x^{(i)} + \alpha\hat{p} i+1i + 1 ∥e∥/∥b∥\|e\|/\|b\|
同上 v=0v = 0 でそれ以外 DIVERGED_BREAKDOWN x(i)+αp̂x^{(i)} + \alpha\hat{p} i+1i + 1 ∥e∥/∥b∥\|e\|/\|b\|
更新の後 相対残差が非有限 DIVERGED_NANORINF x(i+1)x^{(i+1)} i+1i + 1 その非有限値
同上 相対残差 <tol< tol CONVERGED_RTOL x(i+1)x^{(i+1)} i+1i + 1 その相対残差
収束判定の後 ω=0\omega = 0 またはρ(i+1)=0\rho^{(i+1)} = 0 (β\betaを作れない) DIVERGED_BREAKDOWN x(i+1)x^{(i+1)} i+1i + 1 その相対残差
NN回の反復の後 上に当たらない DIVERGED_ITS x(N)x^{(N)} NN 最後の相対残差

 v=Aê=0v = A\hat{e} = 0はeeが 0 となる「幸運な破綻」である. このときω\omegaは0/00/0になるので作らず, x(i)+αp̂x^{(i)} + \alpha\hat{p}で打ち切る. ω=0\omega = 0またはρ(i+1)=0\rho^{(i+1)} = 0の検出は収束判定の後に行うので, 収束した反復では破綻としない. いずれの判定も全ランクで集約した内積から行うので, 全ランクが同じ分岐を取る. ∥b∥=0\|b\| = 0の場合は線形ソルバに共通の扱いによる.

 rank 0 は反復ごとに反復回数 : residual norm = ...の行を書く (v=0v = 0で打ち切った反復では∥e∥/∥b∥\|e\|/\|b\|). v=0v = 0以外の破綻ではpbicgstab breakdown :に続けて原因 (<r0,q> = 0, <r0,q> is not finite, omega (c3) = 0, rho (<r0,r>) = 0) と反復回数を書く. pcg と同じく, 真の相対残差∥b−Ax∥/∥b∥\|b - Ax\| / \|b\|は終了時に計算してfinish : residual true normの行に書き, 真の残差として返すだけである.

 内積の計算精度を FP16 にした構成では, 相対残差が精度の下限に近づくと⟨r*,q⟩\langle r^{\ast},q \rangleが 0 または非有限となり, DIVERGED_BREAKDOWN で終わることがある (利用者ガイドの「低精度での既知の限界」).

2.3 pgmres

 収束判定は各リスタートjj (j=0,1,…,J−1j = 0, 1, \ldots, J - 1. J=⌈N/m⌉J = \lceil N/m \rceil) の先頭で, その時点の近似解x(j)x^{(j)} (x(0)x^{(0)}は初期値) から計算した真の残差r=b−Ax(j)r = b - Ax^{(j)}の相対残差∥r∥/∥b∥\|r\| / \|b\|により行う. 満たさなければv1=r/∥r∥v_{1} = r / \|r\|からAK−1AK^{-1}の Arnoldi 過程をmm列進め, 残差ノルムを最小にする修正でx(j+1)x^{(j+1)}を求めて次のリスタートに進む (方法の全体は利用者ガイドのアルゴリズム). Arnoldi 過程の途中では判定しない. Givens 回転で得る残差ノルム (回転後の右辺の最終成分) は判定に用いず, 幸運な破綻 (次段落) が起きない限りmm列を作ってから解を更新する. 結果は次のとおりである.

条件 収束状態 解 反復回数 残差
リスタートjjの先頭で相対残差が非有限 DIVERGED_NANORINF x(j)x^{(j)} jmjm その非有限値
リスタートjjの先頭で相対残差 <tol< tol CONVERGED_RTOL x(j)x^{(j)} jmjm その相対残差
リスタートjjの Arnoldi 過程でhk,ih_{k,i}またはhi+1,ih_{i+1,i}が非有限 DIVERGED_NANORINF x(j)x^{(j)} (更新しない) jmjm リスタートjjの先頭の相対残差
リスタートjjの幸運な破綻で, 更新に使える列が無い (1 列目でHHが特異) DIVERGED_BREAKDOWN (注) x(j)x^{(j)} (更新しない) jmjm 終了時の真の相対残差
JJ回のリスタートを終えた 終了時の真の相対残差がtoltol未満なら CONVERGED_RTOL, 非有限なら DIVERGED_NANORINF, それ以外は DIVERGED_ITS x(J)x^{(J)} NN 終了時の真の相対残差

 (注) 終了時の真の相対残差がtoltol未満なら CONVERGED_RTOL とする (xxを更新していないので, 通常は起きない).

 反復回数はリスタート回数とmmの積として数える (幸運な破綻で列を打ち切ったリスタートもmmと数える). NNがmmの倍数でない場合は, 最後のリスタートだけN−(J−1)mN - (J-1)m列で Arnoldi 過程を止め, その列数で最小二乗問題を解いて解を更新する. したがって反復上限に達した場合の反復回数はNNちょうどである (N<mN < mでもNN回反復する). NNがmmの倍数なら, すべてのリスタートがmm列である. 真の相対残差は終了時にも計算してfinish : residual true normの行に書き, 真の残差として返す. rank 0 は各リスタートの先頭で反復回数 : residual norm = ...の行を書く. ∥b∥=0\|b\| = 0の場合は線形ソルバに共通の扱いによる.

 Arnoldi 過程のii列目では, w=AK−1viw = AK^{-1}v_{i}をv1,…,viv_{1},\ldots,v_{i}に対して直交化し, その係数をhk,ih_{k,i} (k=1,…,ik = 1,\ldots,i), 直交化後のノルム∥w∥\|w\|をhi+1,ih_{i+1,i}とする. hi+1,ih_{i+1,i}が, 直交化前のwwのノルム∑k≤ihk,i2+hi+1,i2\sqrt{\sum_{k \leq i} h_{k,i}^{2} + h_{i+1,i}^{2}}の10−1410^{-14}倍以下 (または 0) になった場合は, Krylov 部分空間が不変になった「幸運な破綻」とみなす. hi+1,i=0h_{i+1,i} = 0としてii列目にも Givens 回転を施し, その列で Arnoldi 過程を打ち切る. 回転後の対角要素hi,ih_{i,i}が 0 でなく有限ならば先頭ii列, そうでなければ先頭i−1i - 1列で最小二乗問題を解いてx(j+1)x^{(j+1)}を求め, 次のリスタートの先頭で真の残差により判定する. rank 0 はpgmres : Arnoldi breakdown at column ...の行を書く. 使える列が無い (i=1i = 1でh1,1h_{1,1}が 0) 場合は上表のとおり DIVERGED_BREAKDOWN で終える.

 直交化の方式を古典 Gram-Schmidt とした場合は, 既定の修正 Gram-Schmidt 法 (hk,i=⟨w,vk⟩h_{k,i} = \langle w,v_{k} \rangleの計算とw=w−hk,ivkw = w - h_{k,i}v_{k}の更新をk=1,…,ik = 1,\ldots,iの順に行う) の代わりに, hk,i=⟨w,vk⟩h_{k,i} = \langle w,v_{k} \rangle (k=1,…,ik = 1,\ldots,i) をまとめて計算し (集団通信 1 回), w=w−∑khk,ivkw = w - \sum_{k} h_{k,i}v_{k}とする.

2.4 pcagmres

 本節はQQを作る場合 (QQの作り方が AUTO・EXPLICIT) の扱いである. IMPLICIT の扱いは次節に示す. 方法の全体は利用者ガイドのアルゴリズムに示す.

 収束判定は pgmres (pgmres) と同じく, 各リスタートjj (j=0,1,…,J−1j = 0, 1, \ldots, J - 1. J=⌈N/(st)⌉J = \lceil N/(st) \rceil) の先頭で, 真の残差r=b−Ax(j)r = b - Ax^{(j)}の相対残差∥r∥/∥b∥\|r\| / \|b\|により行う. 基底の生成と Givens 回転の途中では判定せず, 幸運な破綻 (下記) が起きない限り 1 回のリスタートでss本ずつttブロック, 計stst本の基底を作ってから解を更新する. Givens 回転は, tt個のブロックぶんの Hessenberg 行列を組み立ててからまとめて行う. 反復の前にも初期残差で判定する (線形ソルバに共通の扱い). 結果は次のとおりである.

条件 収束状態 解 反復回数 残差
反復の前に初期残差の相対残差 <tol< tol CONVERGED_RTOL 初期値 (変えない) 0 初期残差の相対残差 (真の残差も同じ値)
リスタートjjの先頭で相対残差が非有限 DIVERGED_NANORINF x(j)x^{(j)} jstjst その非有限値
リスタートjjの先頭で相対残差 <tol< tol CONVERGED_RTOL x(j)x^{(j)} jstjst その相対残差
リスタートjjの幸運な破綻で, 有効な列が 1 本も無い DIVERGED_BREAKDOWN (pgmres と同じ注) x(j)x^{(j)} (更新しない) jstjst 終了時の真の相対残差
JJ回のリスタートを終えた pgmres と同じく終了時の真の相対残差で決める x(J)x^{(J)} NN 終了時の真の相対残差

 反復回数はリスタート回数とststの積 (作った基底ベクトルの総数) として数える. NNがststの倍数でない場合は, 最後のリスタートで端数N−(J−1)stN - (J-1)st列だけを使って最小二乗問題を解く (解はその反復回数の GMRES と同じ). 基底はss本単位のブロックで作るので, 最後のブロックで使わない基底 (最大s−1s - 1本) の SpMV と前処理が余分に実行される (反復回数には数えない). 反復上限に達した場合の反復回数はNNちょうどである. 反復の前の判定で戻る場合はfinish : residual true normの行を書かない. それ以外の場合の終了時の真の相対残差, rank 0 が書く途中経過の行, ∥b∥=0\|b\| = 0の扱いは pgmres と同じである. Hessenberg 行列の非有限値は DIVERGED_NANORINF にせず, 次に述べるとおり有効な列から外す.

 CA-GMRES では, ブロックの途中で Krylov 部分空間が不変になると, それ以降の基底は前の基底の一次結合になる. この幸運な破綻は Arnoldi のhi+1,i=0h_{i+1,i} = 0ではなく, QR 分解で得る上三角因子RRの対角要素がほぼ 0 になること (階数落ち) として現れる. PARCEL は各ブロックの QR 分解 (最初のブロックではs+1s + 1本の基底, 以降のブロックでは前のブロックまでのQQに対して直交化したss本の基底) の後に, RRの各列について対角要素|Rjj||R_{jj}|をその列のノルム (前のブロックに対して取り除いた成分を含む) と比べ, τ\tau倍以下 (0 または非有限を含む) となる最初の列を階数落ちとみなす. τ\tauは, QR 分解の計算精度の単位丸め誤差uuから決まる値 (古典・修正 Gram-Schmidt では103u10^{3}u, Cholesky QR では102u10^{2}\sqrt{u}) と, 基底のデータ精度の単位丸め誤差ubu_{b}による揺らぎ10ub10u_{b}の大きい方とする. 両者が同じ精度なら前者になる. 階数落ちした列より後ろはRRを単位行列に置き換えてから Hessenberg 行列を組み, その列より前だけを有効とし (その列の非対角要素まで非有限なら, さらに 1 列手前まで), そのリスタートの基底生成を打ち切る. rank 0 はpcagmres : rank-deficient basis blockの行を書く. さらに Givens 回転の際に各列のhi+1,ih_{i+1,i}を列のノルムと比べ, 10−1410^{-14}倍以下なら pgmres と同じくその列で打ち切り, 列に非有限の要素があればその手前で打ち切る (rank 0 はpcagmres : Arnoldi breakdown, solve with ... columnsの行を書く). 有効な列がℓ<st\ell < st本となった場合は, 先頭ℓ\ell列だけで最小二乗問題を解いて解を更新し, 次のリスタートの先頭で判定する. これらの行は階数落ちを検出して有効な列だけで解いたという記録であり, 失敗を意味しない (倍精度でもs=8s = 8の単項式基底が悪条件になると表示される). 有効な列が 1 本も無い場合は上表のとおり DIVERGED_BREAKDOWN で終える.

 AUTO (既定) では, t=1t = 1かつ QR 分解が Cholesky QR の場合に限り正規直交基底QQを陽に作らず, 解の更新で∑kykqk\sum_{k} y_{k}q_{k}の代わりに基底VVとR−1yR^{-1}yの積 (V=QRV = QR) を用いる. EXPLICIT では, この場合もQQを作る.

2.5 pcagmres (QQを作らない場合)

 QQの作り方を IMPLICIT とした場合も, 収束判定, 収束状態と返す値, 幸運な破綻の扱いはQQを作る場合 (前節) と同じである. 終了時の真の相対残差を計算し, 真の残差として返す. 方法の全体は利用者ガイドのアルゴリズムに示す. 異なるのは次の点である.

 QR 分解をモーメント法による Cholesky QR とした場合は, 最初のブロックの Gram 行列を QR分解の章に示すモーメント法で作る (以降のブロックは上と同じく基底の内積から作る). 使える条件はQQの作り方と QR 分解に示す.

2.6 power

 反復ii (i=0,1,…i = 0, 1, \ldots) では, x(i)x^{(i)}からy=Azy = Az (z=x(i)z = x^{(i)}. 前処理後の行列のスペクトルを求める場合はz=K−1x(i)z = K^{-1}x^{(i)}) と Rayleigh 商λ(i)=⟨x(i),y⟩/⟨x(i),x(i)⟩\lambda^{(i)} = \langle x^{(i)},y \rangle / \langle x^{(i)},x^{(i)} \rangleを求め, x(i+1)=y/∥y∥x^{(i+1)} = y / \|y\|とする (x(0)x^{(0)}は大域行番号から作る初期ベクトルで, 正規化しない. 各ランクの先頭行はMPI_Exscanで求めるので, 初期ベクトルは行分割によらない. 方法の全体は利用者ガイドのアルゴリズム). 収束判定は固有値推定の相対変化δ(i)=|λ(i)−λ(i−1)|/|λ(i)|\delta^{(i)} = |\lambda^{(i)} - \lambda^{(i-1)}| / |\lambda^{(i)}| (i≥1i \geq 1) で, 毎反復の最後に行う. λ(i)=0\lambda^{(i)} = 0の場合は|λ(i−1)||\lambda^{(i-1)}|で割り, 両方 0 ならδ(i)=0\delta^{(i)} = 0とする. 残差∥Ay−λy∥\|Ay - \lambda y\| (AK−1AK^{-1}のモードでは∥AK−1y−λy∥\|AK^{-1}y - \lambda y\|) は停止条件に用いていない. 結果は次のとおりである (反復の中で上の行から順に調べる).

条件 収束状態 固有値 固有ベクトル 反復回数 残差
⟨x(i),x(i)⟩\langle x^{(i)},x^{(i)} \rangle, ⟨y,y⟩\langle y,y \rangle, ⟨x(i),y⟩\langle x^{(i)},y \rangle, λ(i)\lambda^{(i)}のいずれかが非有限 DIVERGED_NANORINF 最後の有限な推定値λ(i−1)\lambda^{(i-1)} (i=0i = 0では 0) x(i)x^{(i)} i+1i + 1 NaN
yyが厳密に 0 (⟨y,y⟩=0\langle y,y \rangle = 0) DIVERGED_BREAKDOWN λ(i−1)\lambda^{(i-1)} (i=0i = 0では 0) x(i)x^{(i)} i+1i + 1 δ(i−1)\delta^{(i-1)} (i≤1i \leq 1では NaN)
δ(i)\delta^{(i)}が非有限 DIVERGED_NANORINF λ(i−1)\lambda^{(i-1)} x(i)x^{(i)} i+1i + 1 NaN
δ(i)<tol\delta^{(i)} < tol CONVERGED_RTOL λ(i)\lambda^{(i)} yy i+1i + 1 δ(i)\delta^{(i)}
NN回の反復で上に当たらない DIVERGED_ITS λ(N−1)\lambda^{(N-1)} 最後のyy NN δ(N−1)\delta^{(N-1)}

 固有ベクトルとして返すyyはx(i+1)x^{(i+1)}と同じ向きで, 正規化はしない. 表のx(i)x^{(i)}はi≥1i \geq 1では正規化済みであり, i=0i = 0では初期ベクトルである. yyが厳密に 0 になるのは, x(i)x^{(i)}が零空間にある場合, または低精度で全要素がアンダーフローした場合であり, x(i+1)x^{(i+1)}を作る正規化で 0 による除算となるので反復を打ち切る. 非有限値とy=0y = 0で打ち切った場合は, rank 0 がpower : non-finite value at itr = ...またはpower : A K^-1 x is exactly zero at itr = ... (breakdown)の行を書く. 判定に用いる値はいずれも全ランクで集約した値なので, 全ランクが同じ反復で止まる. rank 0 はi<10i < 10とiiが 50 の倍数の反復でi : Eigen Value = ...の行を書く.

 絶対値最大の固有値が実数で, 絶対値が 2 番目の固有値と分離していることを前提とする (検査しない). 求める側の端の固有値が複素共役対の場合と, 絶対値の等しい固有値が複数ある場合 (例えば±λ\pm\lambda) には収束しないので, ks_arnoldi を使う.

2.7 inverse_power

 AAのモード (前処理後の行列のスペクトルを求めない場合) では, 内部の線形ソルバの前処理KinK_{in}を内部線形ソルバの前処理で指定する (前処理なしも指定できる). 外側の前処理の設定は使わない. KinK_{in}は内部反復の収束を速めるだけで, 返す固有値はKinK_{in}によらずAAの固有値である. AK−1AK^{-1}のモードでは, 内部の pgmres が(AK−1)y=x(i)(AK^{-1})y = x^{(i)}を解いた内部変数yy (最後にK−1K^{-1}を掛けない) を受け取る. このときθ(i)\theta^{(i)}はyyにおけるAK−1AK^{-1}の Rayleigh 商となり, AK−1AK^{-1}の絶対値最小の固有値に収束する. 返す固有ベクトルはAK−1AK^{-1}の右固有ベクトルである. KKはべき乗法と同じく前処理の設定のままAAから一度だけ作る. AAが対称定値の場合は, 内部線形ソルバの種類を pcg とする方が 1 反復あたりの演算と集団通信が少なく速い. 求まる固有値は同じである.

 反復ii (i=0,1,…i = 0, 1, \ldots) では, 内部の線形ソルバでAy=x(i)Ay = x^{(i)} (AK−1AK^{-1}のモードでは(AK−1)y=x(i)(AK^{-1})y = x^{(i)}) を初期値y=0y = 0から解き, θ(i)=⟨y,x(i)⟩/⟨y,y⟩\theta^{(i)} = \langle y,x^{(i)} \rangle / \langle y,y \rangleとx(i+1)=y/∥y∥x^{(i+1)} = y / \|y\|を求める (方法の全体は利用者ガイドのアルゴリズム). x(0)x^{(0)}はべき乗法と同じ初期ベクトルを正規化したものである (ノルムが 0 または非有限の場合は正規化を省き, rank 0 がその旨を表示する). 収束判定はべき乗法と同じく固有値推定の相対変化δ(i)=|θ(i)−θ(i−1)|/|θ(i)|\delta^{(i)} = |\theta^{(i)} - \theta^{(i-1)}| / |\theta^{(i)}| (i≥1i \geq 1. 分母が 0 の場合の扱いもべき乗法と同じ) で, 毎反復の最後に行う. 内部の線形ソルバが DIVERGED_NANORINF 以外の理由で収束しなかった場合は外側の反復を続け, その回数を内部線形ソルバの失敗回数に数える. 結果は次のとおりである (反復の中で上の行から順に調べる).

条件 収束状態 固有値 固有ベクトル 反復回数 残差
内部の線形ソルバが DIVERGED_NANORINF で終わった DIVERGED_NANORINF 最後の有限なθ(i−1)\theta^{(i-1)} (i=0i = 0では 0) x(i)x^{(i)} i+1i + 1 NaN
⟨y,x(i)⟩\langle y,x^{(i)} \rangle, ⟨y,y⟩\langle y,y \rangleのいずれかが非有限 DIVERGED_NANORINF θ(i−1)\theta^{(i-1)} x(i)x^{(i)} i+1i + 1 NaN
内部の線形ソルバの解yyが厳密に 0 DIVERGED_BREAKDOWN θ(i−1)\theta^{(i-1)} x(i)x^{(i)} i+1i + 1 δ(i−1)\delta^{(i-1)} (i≤1i \leq 1では NaN)
θ(i)\theta^{(i)}, δ(i)\delta^{(i)}のいずれかが非有限 DIVERGED_NANORINF θ(i−1)\theta^{(i-1)} x(i)x^{(i)} i+1i + 1 NaN
δ(i)<tol\delta^{(i)} < tol CONVERGED_RTOL θ(i)\theta^{(i)} x(i+1)x^{(i+1)} i+1i + 1 δ(i)\delta^{(i)}
NN回の反復で上に当たらない DIVERGED_ITS θ(N−1)\theta^{(N-1)} x(N)x^{(N)} NN δ(N−1)\delta^{(N-1)}

 返す固有ベクトルは正規化済みである. 打ち切った場合は rank 0 がinverse_power :で始まる 1 行でその旨を表示する. 判定に用いる値が全ランクで同じになる点, rank 0 が書く途中経過の行はべき乗法と同じである. 内部の線形ソルバの誤差はそのままθ(i)\theta^{(i)}の誤差になるため, 外側のtoltolより内部の線形ソルバを厳しく収束させる必要がある.

 AAが正則で, 絶対値最小の固有値が実数であることを前提とする (検査しない). 絶対値最小の固有値が複素共役対になる非対称行列では Rayleigh 商が収束しないので, ks_arnoldi の shift-invert をσ=0\sigma = 0で使う.

2.8 ks_arnoldi

 Op\mathrm{Op}は Arnoldi 過程を適用する演算子であり, Ritz 対(θ,x)(\theta, x)はOp\mathrm{Op}の近似固有対である (記号). 方法の全体は利用者ガイドのアルゴリズムに示す. shift-invert では(A−σI)z=v(A - \sigma I)z = v (または(AK−1−σI)z=v(AK^{-1} - \sigma I)z = v) を各 Arnoldi ステップで内部の pgmres (右前処理, 直交化は修正 Gram-Schmidt 法) により解く. 内部 pgmres の前処理は固有値ソルバの補足に, 収束判定値などの既定値は設定に示す.

 Arnoldi 過程はv1=x(0)/∥x(0)∥v_{1} = x^{(0)} / \|x^{(0)}\| (x(0)x^{(0)}は初期ベクトル) から始める. ∥x(0)∥\|x^{(0)}\|が 0 または非有限の場合は, x(0)x^{(0)}をべき乗法と同じ既定の初期ベクトル (大域行番号から作る. rank 0 がその旨を表示する) に置き換える. jj列目ではw=Opvjw = \mathrm{Op}\,v_{j}をVj=[v1,…,vj]V_{j} = [v_{1},\ldots,v_{j}]に対して直交化し, 係数をhi,jh_{i,j} (i≤ji \leq j), 直交化後のノルムをhj+1,j=∥w∥h_{j+1,j} = \|w\|としてvj+1=w/hj+1,jv_{j+1} = w / h_{j+1,j}とする. HHはhi,jh_{i,j}を要素に持つm×mm \times mの行列である.

 直交化は古典 Gram-Schmidt 法を 2 回適用する CGS2 [6] で行う (ξ=VjTw\xi = V_{j}^{T}w, w=w−Vjξw = w - V_{j}\xiを 2 回繰り返し, 係数ξ\xiの和をh1:j,jh_{1:j,j}とする. QR分解の章を参照). 1 回目の射影で残った成分を 2 回目で除去し, 基底の直交性を保つ. 1 パスあたりの内積は集団通信 1 回で集約する. 直交化の方式を修正 Gram-Schmidt にすると, 修正 Gram-Schmidt 法を 2 回適用する方法 (列ごとに内積・集団通信・axpy) に替わる. どちらも 2 回目で直交性を回復し, 固有値の精度は同等である. 1 ランクの局所行数が小さい CPU の構成では修正 Gram-Schmidt 法が速い場合があり, 局所行数が大きい CPU と GPU では CGS2 が速い. 乱数方向の直交化 (下記) も同じ方法で行う. 再直交化により多重固有値での偽の固有値 (ghost eigenvalue) を抑えられるため, locking・deflation は実装していない.

 リスタートの縮約Vk=VmQ:,1:kV_{k} = V_{m}Q_{:,1:k}は基底VVの中で行い, 2 本目の基底を確保しない (double-double を含まない型で, kkeep+1≤32k_{keep} + 1 \leq 32の場合. それ以外では 2 本目の基底 (m+1m + 1列) を確保する).

 収束判定は, 各リスタートで Arnoldi 分解をmm列まで広げた後に 1 回行う. HHの固有対(θl,yl)(\theta_{l}, y_{l})を|θl||\theta_{l}|の降順に並べ, 先頭nevnev個の Ritz 対(θl,Vmyl)(\theta_{l}, V_{m}y_{l})について, Op\mathrm{Op}に対する相対残差∥Opx−θx∥/(|θ|∥x∥)\|\mathrm{Op}\,x - \theta x\| / (|\theta|\|x\|)の推定値|hm+1,m||emTyl|/|θl||h_{m+1,m}||e_{m}^{T}y_{l}| / |\theta_{l}| (eme_{m}は第mm単位ベクトル) をtoltolと比べる. 複素共役対の場合は実部・虚部の 2 成分のノルムを用いる. |θl|<10−300|\theta_{l}| < 10^{-300}の Ritz 対は満たさない側に数える. shift-invert では判定はθ\theta (変換前の値) に対して行われる. nevnev個すべてがtoltol以下なら収束とする. 満たさなければHHの実 Schur 分解を並べ替えて|θ||\theta|の大きい Ritz 値を先頭に集め, そのkk本 (kkeepk_{keep}本. 複素共役対は 2 本を同時に保持するためkkeep+1k_{keep} + 1本となる場合がある) の Schur ベクトルを保持して次のリスタートに進む. 1 サイクル目はmm回, 2 サイクル目以降はm−km - k回のOp\mathrm{Op}の適用で Arnoldi 分解をmm列に戻す. 結果は次のとおりである.

条件 収束状態 残差
Arnoldi 過程でhi,jh_{i,j}またはhj+1,jh_{j+1,j}が非有限 DIVERGED_NANORINF それまでの値
判定対象の Ritz 値または残差推定が非有限 DIVERGED_NANORINF NaN
nevnev個の残差推定がtoltol以下 (基底に乱数方向を含まない) CONVERGED_RTOL 残差推定の最大値
同 (基底に乱数方向を含む) で, 真の残差もtoltol以下 CONVERGED_RTOL 真の残差の最大値
同 (基底に乱数方向を含む) で, 真の残差がtoltolを超える DIVERGED_BREAKDOWN 真の残差の最大値
不変部分空間 (下記) で, 真の残差をtoltol以下と確かめた CONVERGED_RTOL 真の残差の最大値
不変部分空間を真の残差で確かめられないまま止めた (乱数方向の上限, 空間が尽きた) DIVERGED_BREAKDOWN 残差推定の最大値
不変部分空間の有効次元がnevnev未満 DIVERGED_BREAKDOWN それまでの値
不変部分空間に達したのに判定を満たさない DIVERGED_BREAKDOWN 残差推定の最大値
LAPACK の失敗 (下記) DIVERGED_BREAKDOWN それまでの値
NRN_{R}回のリスタートで上に当たらない DIVERGED_ITS 最後の残差推定の最大値

 「それまでの値」は直前のリスタートで求めた値であり, 1 回目のリスタートで止まった場合は NaN である. 反復回数は途中で止まった回を含む, 実行したリスタートの回数である. どの場合も, 最後のHH (不変部分空間で止めた場合は有効次元の先頭ブロック) の固有分解をし直して Ritz 対を作り, 出力する (NRN_{R}回のリスタートで収束しなかった場合も最後の Ritz 対を返す).

 hj+1,jh_{j+1,j}が, 直交化前のwwのノルム∑i≤jhi,j2+hj+1,j2\sqrt{\sum_{i \leq j} h_{i,j}^{2} + h_{j+1,j}^{2}}の10−1410^{-14}倍以下 (または 0) になった場合は, Krylov 部分空間が不変になった (不変部分空間) とみなし, hj+1,j=0h_{j+1,j} = 0とする. このとき Ritz 対の残差推定は 0 となるが, 低精度の基底では, 直交化後のwwが桁落ちやアンダーフローで 0 になり, 偽の不変部分空間となることがあるため, 次のように扱う.

 有効次元がkkeepk_{keep}より小さいまま終えた場合は, 足りない固有値・固有ベクトルを 0 として返す (rank 0 がその旨を表示する).

 HHの固有分解は LAPACK のdgeev, リスタートのための実 Schur 分解と並べ替えはdgees・dtrsenでホスト側で計算する. これらは rank 0 だけが計算して結果を全ランクに配る (HHも rank 0 の値に揃える) ので, 丸めの差で分岐がランクごとに割れることはない. LAPACK が失敗した (info が 0 でない. dtrsenの後に保持する本数が 1 以上mm未満でない場合を含む) 場合は DIVERGED_BREAKDOWN とする. |θ||\theta|による並べ替えでは NaN を最後に回す. 途中の判定と打ち切りの理由は, rank 0 が[KS]で始まる行に書く.

 出力は|θ||\theta|の降順にkkeepk_{keep}個である (収束判定の対象は先頭nevnev個. 固有値と固有ベクトルの出力). shift-invert では|θ||\theta|の大きい順がσ\sigmaに近い順に当たる. shift-invert の逆変換で|θ|2≤10−300|\theta|^{2} \leq 10^{-300}となる Ritz 値は, 固有値として+∞+\inftyを返す.