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

8 線形ソルバ

 本ライブラリルーチンで用いた各反復法アルゴリズムについて紹介する. 以下では, nglobal×nglobaln_{global} \times n_{global}の実行列AAを係数行列に持つ連立一次方程式Ax=bAx = bを解くものとする. 各節では, アルゴリズムとその記号を示す. 収束判定の詳細, 破綻と非有限値の扱い, 返す値は, API リファレンスの各ソルバのsolver()の節に示す (線形ソルバに共通の扱い). ⟨⋅,⋅⟩\langle \cdot,\cdot \rangleは内積, ∥⋅∥\|\cdot\|は 2 ノルムである. 4 つの線形ソルバ (pcg, pbicgstab, pgmres, pcagmres) の収束判定はいずれも相対残差∥r∥/∥b∥\|r\| / \|b\|とset_tolerance()の値toltolとの比較 (∥r∥/∥b∥<tol\|r\| / \|b\| < tolで収束) である. 各解法が扱える行列と特徴を次に示す.

解法 クラス 対象の行列 特徴
前処理付共役勾配法 parcel::krylov::pcg 対称正定値 (前処理行列も対称正定値) 1 反復あたりの演算と集団通信が少ない
前処理付安定化双共役勾配法 parcel::krylov::pbicgstab 対称・非対称 右前処理. 1 反復に SpMV と前処理を 2 回ずつ行う. 残差は単調に減るとは限らない
前処理付一般化最小残差法 parcel::krylov::pgmres 対称・非対称 右前処理. リスタート周期mmの中で残差ノルムを最小化する
前処理付通信削減型一般化最小残差法 parcel::krylov::pcagmres 対称・非対称 (モーメント法は対称・前処理なしのみ) 右前処理. ss本の基底をまとめて作って直交化し, GMRES(stst) と同等の反復を少ない集団通信で行う. 正規直交基底QQを陽に作るかどうかをset_explicit_q()で選べる (作らない場合は Gram 行列の Cholesky 分解で直交化する)

 本書のアルゴリズムと数式では, 反復番号を括弧付きの上付き (x(i)x^{(i)}, α(i)\alpha^{(i)}) で, ベクトルの成分と, ベクトルの組の中の番号を下付き (xix_{i}, vjv_{j}) で表す. 括弧の無い上付きはべき乗 ((AK−1)s(AK^{-1})^{s}), ATA^{T}は転置, A−1A^{-1}は逆行列である. 行列は大文字, ベクトルとスカラーは小文字の斜体で書き, 英語のキーワードと関数名 (solve\mathrm{solve}, chol\mathrm{chol} など) は立体で書く. nglobaln_{global}は行列の次数 (大域の行数), nlocaln_{local}は各ランクが担当する行数である. 記号は節ごとに定義し, 別の節では別の意味に使うことがある.

 収束状態の定数と各ソルバでの意味は API リファレンスの「収束状態の定数と標準出力」 にまとめる.


8.1 前処理付共役勾配法[1]

 共役勾配法(CG法)は対称行列向けの Krylov 部分空間法である. 係数行列AAと前処理行列KKはともに対称正定値であることを仮定する.

 x(0)x^{(0)}はsolver()の引数xに与えた初期値, KKはset_precon_algo()などで指定した前処理行列 (前処理の章を参照. 前処理なしではK=IK = I), toltolはset_tolerance()で指定する収束判定値 (既定 1.0e-8), NNはset_max_iteration()で指定する最大反復回数 (既定 10000) である. zzは前処理を施した残差, p(i)p^{(i)}は探索方向, q(i)q^{(i)}はAp(i)Ap^{(i)}, ρ(i)\rho^{(i)}・α(i)\alpha^{(i)}・β(i)\beta^{(i)}・γ\gammaはスカラーである.

  1. Computer(0)=b−Ax(0)forsomeinitialguessx(0)\mathrm{Compute}\ r^{(0)} = b - Ax^{(0)}\ \mathrm{for}\ \mathrm{some}\ \mathrm{initial}\ \mathrm{guess}\ x^{(0)}
  2. p(−1)=0p^{(-1)} = 0
  3. β(−1)=0\beta^{(-1)} = 0
  4. solvezfromKz=r(0)\mathrm{solve}\ z\ \mathrm{from}\ Kz = r^{(0)}
  5. ρ(0)=⟨z,r(0)⟩\rho^{(0)} = \langle z,r^{(0)} \rangle
  6. fori=0,1,…,N−1\mathrm{for}\ i = 0,1,\ldots,N - 1
  7.   p(i)=z+β(i−1)p(i−1)p^{(i)} = z + \beta^{(i - 1)}p^{(i - 1)}
  8.   q(i)=Ap(i)q^{(i)} = Ap^{(i)}
  9.   γ=⟨p(i),q(i)⟩\gamma = \langle p^{(i)},q^{(i)} \rangle
  10.   α(i)=ρ(i)/γ\alpha^{(i)} = \rho^{(i)}\ /\ \gamma
  11.   x(i+1)=x(i)+α(i)p(i)x^{(i + 1)} = x^{(i)} + \alpha^{(i)}p^{(i)}
  12.   r(i+1)=r(i)−α(i)q(i)r^{(i + 1)} = r^{(i)} - \alpha^{(i)}q^{(i)}
  13.   if∥r(i+1)∥/∥b∥<tolthen\mathrm{if}\ \|r^{(i + 1)}\|\ /\ \|b\| < tol\ \mathrm{then}
  14.     quit\mathrm{quit}
  15.   endif\mathrm{endif}
  16.   solvezfromKz=r(i+1)\mathrm{solve}\ z\ \mathrm{from}\ Kz = r^{(i + 1)}
  17.   ρ(i+1)=⟨z,r(i+1)⟩\rho^{(i + 1)} = \langle z,r^{(i + 1)} \rangle
  18.   β(i)=ρ(i+1)/ρ(i)\beta^{(i)} = \rho^{(i + 1)}\ /\ \rho^{(i)}
  19. end\mathrm{end}

 実装では, 11 行目のxxの更新を既定では毎反復行い, 探索方向p(i)p^{(i)}は 1 本だけ持つ. 環境変数PARCEL_PSTEPに 2 以上の値kkを指定すると, 探索方向をkk本貯めてkk反復ごとにまとめてxxに反映する (xxのメモリの読み書きが1/k1/kになって少し速くなる代わりに, ベクトルk−1k - 1本分のメモリを使う. 「メモリと速さの選択」). 解は数学的には同じで, 丸めの順序だけが変わる. 収束判定は 12 行目のrrで行うので, 反復回数はPARCEL_PSTEPによらない.

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


8.2 前処理付安定化双共役勾配法[1]

 安定化双共役勾配法(Bi-CGSTAB)は非対称行列向けの Krylov 部分空間法である. 前処理は右前処理として適用する. すなわちAK−1AK^{-1}に対して反復し, 解の更新にはK−1K^{-1}を掛けた方向p̂\hat{p}・ê\hat{e}を用いるので, 残差r(i)r^{(i)}は前処理を施さない残差b−Ax(i)b - Ax^{(i)}に対応する.

 x(0)x^{(0)}はsolver()の引数xに与えた初期値, KKはset_precon_algo()などで指定した前処理行列, toltolはset_tolerance() (既定 1.0e-8), NNはset_max_iteration() (既定 10000) の値である. r(0)r^{(0)}は初期残差, r*=r(0)r^{\ast} = r^{(0)}は双対 (shadow) 残差であり, r*r^{\ast}は反復中は固定して用いる. p(i)p^{(i)}は探索方向, eeは中間の残差, c1c_{1}・c2c_{2}・c3c_{3}・α\alpha・β\betaはスカラーである.

  1. Computer(0)=b−Ax(0)forsomeinitialguessx(0)\mathrm{Compute}\ r^{(0)} = b - Ax^{(0)}\ \mathrm{for}\ \mathrm{some}\ \mathrm{initial}\ \mathrm{guess}\ x^{(0)}
  2. r*=r(0),p(0)=r(0)r^{\ast} = r^{(0)},\ \ p^{(0)} = r^{(0)}
  3. c1=⟨r*,r(0)⟩c_{1} = \langle r^{\ast},r^{(0)} \rangle
  4. fori=0,1,…,N−1\mathrm{for}\ i = 0,1,\ldots,N - 1
  5.   solvep̂fromKp̂=p(i)\mathrm{solve}\ \hat{p}\ \mathrm{from}\ K\hat{p} = p^{(i)}
  6.   q=Ap̂q = A\hat{p}
  7.   c2=⟨r*,q⟩c_{2} = \langle r^{\ast},q \rangle
  8.   ifc2=0orc2isnotfinitethen\mathrm{if}\ c_{2} = 0\ \mathrm{or}\ c_{2}\ \mathrm{is}\ \mathrm{not}\ \mathrm{finite}\ \mathrm{then}
  9.     quit(breakdown)\mathrm{quit}\ (\mathrm{breakdown})
  10.   endif\mathrm{endif}
  11.   α=c1/c2\alpha = c_{1}\ /\ c_{2}
  12.   e=r(i)−αqe = r^{(i)} - \alpha q
  13.   solveêfromKê=e\mathrm{solve}\ \hat{e}\ \mathrm{from}\ K\hat{e} = e
  14.   v=Aêv = A\hat{e}
  15.   if⟨v,v⟩=0then\mathrm{if}\ \langle v,v \rangle = 0\ \mathrm{then}
  16.     x(i+1)=x(i)+αp̂x^{(i + 1)} = x^{(i)} + \alpha\hat{p}
  17.     quit(convergedif∥e∥/∥b∥<tol,otherwisebreakdown)\mathrm{quit}\ (\mathrm{converged}\ \mathrm{if}\ \|e\|\ /\ \|b\| < tol,\ \mathrm{otherwise}\ \mathrm{breakdown})
  18.   endif\mathrm{endif}
  19.   c3=⟨e,v⟩/⟨v,v⟩c_{3} = \langle e,v \rangle\ /\ \langle v,v \rangle
  20.   x(i+1)=x(i)+αp̂+c3êx^{(i + 1)} = x^{(i)} + \alpha\hat{p} + c_{3}\hat{e}
  21.   r(i+1)=e−c3vr^{(i + 1)} = e - c_{3}v
  22.   c1=⟨r*,r(i+1)⟩c_{1} = \langle r^{\ast},r^{(i + 1)} \rangle
  23.   if∥r(i+1)∥/∥b∥<tolthen\mathrm{if}\ \|r^{(i + 1)}\|\ /\ \|b\| < tol\ \mathrm{then}
  24.     quit\mathrm{quit}
  25.   endif\mathrm{endif}
  26.   ifc3=0orc1=0then\mathrm{if}\ c_{3} = 0\ \mathrm{or}\ c_{1} = 0\ \mathrm{then}
  27.     quit(breakdown)\mathrm{quit}\ (\mathrm{breakdown})
  28.   endif\mathrm{endif}
  29.   β=c1/(c2c3)\beta = c_{1}\ /\ (c_{2}c_{3})
  30.   p(i+1)=r(i+1)+β(p(i)−c3q)p^{(i + 1)} = r^{(i + 1)} + \beta(p^{(i)} - c_{3}q)
  31. end\mathrm{end}

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


8.3 前処理付一般化最小残差法[1]

 一般化最小残差法(GMRES(m))は非対称行列向けの Krylov 部分空間法である. mm回の Arnoldi 過程で作った部分空間の中で残差ノルムを最小化して近似解を更新し, それを初期値として反復を再開する (リスタート). PARCEL のpgmresは右前処理であり, AK−1AK^{-1}に対して Arnoldi 過程を行い, 近似解を更新するときにだけK−1K^{-1}を掛ける. そのため最小化する残差は前処理を施さない残差b−Axb - Axそのものである. Arnoldi 過程の直交化法として古典 Gram-Schmidt 法と修正 Gram-Schmidt 法が整備されている.

 x(0)x^{(0)}はsolver()の引数xに与えた初期値, x(j)x^{(j)}はjj回目のリスタートの開始時の近似解, KKはset_precon_algo()などで指定した前処理行列, mmはset_restart()で指定するリスタート周期 (既定 30), toltolはset_tolerance() (既定 1.0e-8) の値である. リスタート回数の上限JJはset_max_iteration()の値NN (既定 10000) からJ=⌈N/m⌉J = \lceil N/m \rceilと決まる (NNがmmの倍数でなければ, 最後のリスタートは端数のN−(J−1)mN - (J-1)m列で打ち切る). viv_{i}は正規直交基底, hk,ih_{k,i}は Hessenberg 行列の要素, cos⁡ϕi\cos\phi_{i}・sin⁡ϕi\sin\phi_{i}は Givens 回転の係数, ζ=(ζ1,…,ζm+1)T\zeta = (\zeta_{1},\ldots,\zeta_{m+1})^{T}は回転を施した右辺ベクトル, HmH_{m}は Givens 回転後のhk,ih_{k,i} (1≤k≤i≤m1 \leq k \leq i \leq m) からなるm×mm \times mの上三角行列, ζ1:m\zeta_{1:m}はζ\zetaの先頭mm成分である. 12〜15 行目はset_qr_algo()で修正 Gram-Schmidt 法 (parcel::qr::QR_MGS, 既定) を選んだ場合を示す. 実装はv1v_{1}とζ\zetaの符号をともに反転して計算するが, 両者の反転は打ち消し合い, 結果は変わらない.

  1. Chooseinitialguessx(0)\mathrm{Choose}\ \mathrm{initial}\ \mathrm{guess}\ x^{(0)}
  2. forj=0,1,…,J−1\mathrm{for}\ j = 0,1,\ldots,J - 1
  3.   r=b−Ax(j)r = b - Ax^{(j)}
  4.   if∥r∥/∥b∥<tolthen\mathrm{if}\ \|r\|\ /\ \|b\| < tol\ \mathrm{then}
  5.     quit\mathrm{quit}
  6.   endif\mathrm{endif}
  7.   v1=r/∥r∥v_{1} = r\ /\ \|r\|
  8.   ζ=(∥r∥,0,…,0)T\zeta = (\|r\|,0,\ldots,0)^{T}
  9.   fori=1,2,…,m\mathrm{for}\ i = 1,2,\ldots,m
  10.     solvev̂ifromKv̂i=vi\mathrm{solve}\ \hat{v}_{i}\ \mathrm{from}\ K\hat{v}_{i} = v_{i}
  11.     w=Av̂iw = A\hat{v}_{i}
  12.     fork=1,2,…,i\mathrm{for}\ k = 1,2,\ldots,i
  13.       hk,i=⟨w,vk⟩h_{k,i} = \langle w,v_{k} \rangle
  14.       w=w−hk,ivkw = w - h_{k,i}v_{k}
  15.     end\mathrm{end}
  16.     hi+1,i=∥w∥h_{i + 1,i} = \|w\|
  17.     vi+1=w/hi+1,iv_{i + 1} = w\ /\ h_{i + 1,i}
  18.     fork=1,2,…,i−1\mathrm{for}\ k = 1,2,\ldots,i - 1
  19.       (hk,ihk+1,i)=(cos⁡ϕk−sin⁡ϕksin⁡ϕkcos⁡ϕk)(hk,ihk+1,i)\begin{pmatrix} h_{k,i} \\ h_{k + 1,i} \end{pmatrix} = \begin{pmatrix} \cos\phi_{k} & -\sin\phi_{k} \\ \sin\phi_{k} & \cos\phi_{k} \end{pmatrix}\begin{pmatrix} h_{k,i} \\ h_{k + 1,i} \end{pmatrix}
  20.     end\mathrm{end}
  21.     cos⁡ϕi=1/1+(hi+1,i/hi,i)2\cos\phi_{i} = 1\ /\ \sqrt{1 + (h_{i + 1,i}\ /\ h_{i,i})^{2}}
  22.     sin⁡ϕi=−cos⁡ϕihi+1,i/hi,i\sin\phi_{i} = -\cos\phi_{i}h_{i + 1,i}\ /\ h_{i,i}
  23.     (ζiζi+1)=(cos⁡ϕi−sin⁡ϕisin⁡ϕicos⁡ϕi)(ζiζi+1)\begin{pmatrix} \zeta_{i} \\ \zeta_{i + 1} \end{pmatrix} = \begin{pmatrix} \cos\phi_{i} & -\sin\phi_{i} \\ \sin\phi_{i} & \cos\phi_{i} \end{pmatrix}\begin{pmatrix} \zeta_{i} \\ \zeta_{i + 1} \end{pmatrix}
  24.     hi,i=cos⁡ϕihi,i−sin⁡ϕihi+1,ih_{i,i} = \cos\phi_{i}h_{i,i} - \sin\phi_{i}h_{i + 1,i}
  25.     hi+1,i=0h_{i + 1,i} = 0
  26.   end\mathrm{end}
  27.   y=Hm−1ζ1:my = H_{m}^{-1}\zeta_{1:m}
  28.   solvex̂fromKx̂=∑k=1mykvk\mathrm{solve}\ \hat{x}\ \mathrm{from}\ K\hat{x} = \sum_{k = 1}^{m} y_{k}v_{k}
  29.   x(j+1)=x(j)+x̂x^{(j+1)} = x^{(j)} + \hat{x}
  30. end\mathrm{end}

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


8.4 前処理付通信削減型一般化最小残差法 [2,3]

 通信削減型一般化最小残差法(CA-GMRES(s,t))は非対称行列向けの Krylov 部分空間法である. GMRES(m) のss回の反復に相当する基底ベクトルをまとめて生成し, ブロック単位で直交化する. これをtt回繰り返して得たstst本の基底で近似解を更新し, それを初期解として反復を再開する. m=stm = stがGMRES(m)のリスタート周期に相当する. 数学的にはCA-GMRES(s,t)とGMRES(m)の収束性は同等であり, 通信削減型のQR分解を適用することでGMRES(m)よりも集団通信の回数を削減する. ただし, 一度にss本の基底ベクトルを生成するため, ssが過大な場合には, 丸め誤差によって基底ベクトルの直交性が崩れることでGMRESよりも収束性が悪くなる. PARCELの基底は単項式基底 (vi+1=AK−1viv_{i+1} = AK^{-1}v_{i}) のみであり, Newton 基底は実装していない. 前処理はpgmresと同じく右前処理である.

 x(0)x^{(0)}はsolver()の引数xに与えた初期値, x(j)x^{(j)}はjj回目のリスタートの開始時の近似解, KKはset_precon_algo()などで指定した前処理行列, ss・ttはset_restart(s, t)で指定する値 (既定s=8s = 8, t=4t = 4), toltolはset_tolerance() (既定 1.0e-8) の値である. リスタート回数の上限JJはset_max_iteration()の値NN (既定 10000) からJ=⌈N/(st)⌉J = \lceil N/(st) \rceilと決まる (NNがststの倍数でなければ, 最後のリスタートは端数の列だけで最小二乗問題を解く). 19 行目・26 行目の QR 分解の方法はset_qr_algo()で選ぶ (parcel::qr::QR_CGS, QR_MGS (既定), QR_CHOLESKYQR. QR分解の章を参照). 以下のアルゴリズムは正規直交基底QQを陽に作る場合である. QQを作らない場合は後述する.

 B_=[e2,…,es+1]\underline{B} = [e_{2},\ldots,e_{s+1}]は単項式基底の基底変換行列 ((s+1)×s(s+1) \times s. ele_{l}は第ll単位ベクトル), BBはその先頭ss行, bkb_{k}はB_\underline{B}のs+1s+1行ss列要素である. 下線を付けた記号は, 付けない記号より 1 本 (1 列・1 行) 多い版を表す. V_k=[vsk+1,…,vs(k+1)+1]\underline{V}_{k} = [v_{sk+1},\ldots,v_{s(k+1)+1}]はkk番目のブロックで生成するs+1s+1本の基底, VkV_{k}はその先頭を除くss本である. Q=[q1,q2,…]Q = [q_{1}, q_{2}, \ldots]は正規直交化した基底であり, Q1:mQ_{1:m}はその先頭mm列を表す. P_0\underline{P}_{0}・R_0\underline{R}_{0}はV_0\underline{V}_{0}の QR 分解の因子, PkP_{k}・SkS_{k}はVkV_{k}の QR 分解の因子である. C_k\underline{C}_{k}はブロック古典 Gram-Schmidt 法の係数行列 ((sk+1)×(s+1)(sk+1) \times (s+1)), CkC_{k}はその先頭の列を除くss列 (VkV_{k}に対応), EkE_{k}はC_k\underline{C}_{k}の先頭ss列から最終行を除いたものである. R_k\underline{R}_{k}は QR 分解で得る(s+1)×(s+1)(s+1) \times (s+1)の上三角行列, RkR_{k}はその先頭ss行ss列, zkz_{k}・ρk\rho_{k}はその第s+1s+1列の上ss成分と対角要素, δk\delta_{k}はRkR_{k}のss行ss列要素である. H_(k)\underline{H}_{(k)}はQ1:s(k+1)+1Q_{1:s(k+1)+1}に対する(s(k+1)+1)×s(k+1)(s(k+1)+1) \times s(k+1)の Hessenberg 行列, H(k)H_{(k)}はその最終行を除いたものである. UkU_{k}とHkH_{k}は, kk番目のブロックでH_(k)\underline{H}_{(k)}に加わるss列のうち, それぞれ前のブロックの行とkk番目のブロックの行の部分であり, γk\gamma_{k}はその最終行の要素である. ζ\zetaは回転を施した右辺ベクトル, ζ1:st\zeta_{1:st}はその先頭stst成分, hk,ih_{k,i}はH_(t−1)\underline{H}_{(t-1)}の(k,i)(k,i)要素, cos⁡ϕi\cos\phi_{i}・sin⁡ϕi\sin\phi_{i}は Givens 回転の係数である. 回転後のH(t−1)H_{(t-1)}は上三角行列となる.

  1. B_=[e2,e3,…,es+1]\underline{B} = [e_{2},e_{3},\ldots,e_{s + 1}]
  2. Chooseinitialguessx(0)\mathrm{Choose}\ \mathrm{initial}\ \mathrm{guess}\ x^{(0)}
  3. forj=0,1,…,J−1\mathrm{for}\ j = 0,1,\ldots,J - 1
  4.   r=b−Ax(j)r = b - Ax^{(j)}
  5.   if∥r∥/∥b∥<tolthen\mathrm{if}\ \|r\|\ /\ \|b\| < tol\ \mathrm{then}
  6.     quit\mathrm{quit}
  7.   endif\mathrm{endif}
  8.   v1=r/∥r∥v_{1} = r\ /\ \|r\|
  9.   ζ=(∥r∥,0,…,0)T\zeta = (\|r\|,0,\ldots,0)^{T}
  10.   fork=0,1,…,t−1\mathrm{for}\ k = 0,1,\ldots,t - 1
  11.     ifk>0then\mathrm{if}\ k > 0\ \mathrm{then}
  12.       vsk+1=qsk+1v_{sk + 1} = q_{sk + 1}
  13.     endif\mathrm{endif}
  14.     fori=1,2,…,s\mathrm{for}\ i = 1,2,\ldots,s
  15.       solvev̂sk+ifromKv̂sk+i=vsk+i\mathrm{solve}\ \hat{v}_{sk + i}\ \mathrm{from}\ K\hat{v}_{sk + i} = v_{sk + i}
  16.       vsk+i+1=Av̂sk+iv_{sk + i + 1} = A\hat{v}_{sk + i}
  17.     end\mathrm{end}
  18.     ifk=0then\mathrm{if}\ k = 0\ \mathrm{then}
  19.       QRdecompositionV_0=P_0R_0\mathrm{QR}\ \mathrm{decomposition}\ \underline{V}_{0} = \underline{P}_{0}\underline{R}_{0}
  20.       Q1:s+1=P_0Q_{1:s+1} = \underline{P}_{0}
  21.       H_(0)=R_0B_R0−1\underline{H}_{(0)} = \underline{R}_{0}\underline{B}R_{0}^{-1}
  22.       γ0=δ0−1ρ0b0\gamma_{0} = \delta_{0}^{-1}\rho_{0}b_{0}
  23.     else\mathrm{else}
  24.       C_k=Q1:sk+1TV_k\underline{C}_{k} = Q_{1:sk+1}^{T}\underline{V}_{k}
  25.       Vk=Vk−Q1:sk+1CkV_{k} = V_{k} - Q_{1:sk+1}C_{k}
  26.       QRdecompositionVk=PkSk\mathrm{QR}\ \mathrm{decomposition}\ V_{k} = P_{k}S_{k}
  27.       Q1:s(k+1)+1=[Q1:sk+1,Pk]Q_{1:s(k+1)+1} = [Q_{1:sk+1},P_{k}]
  28.       R_k=(Rkzk01,sρk)\underline{R}_{k} = \begin{pmatrix} R_{k} & z_{k} \\ 0_{1,s} & \rho_{k} \end{pmatrix}
  29.       Uk=−H(k−1)EkRk−1+C_kB_Rk−1U_{k} = -H_{(k-1)}E_{k}R_{k}^{-1} + \underline{C}_{k}\underline{B}R_{k}^{-1}
  30.       Hk=RkBRk−1+δk−1bkzkesT−γk−1e1eskTEkRk−1H_{k} = R_{k}BR_{k}^{-1} + \delta_{k}^{-1}b_{k}z_{k}e_{s}^{T} - \gamma_{k - 1}e_{1}e_{sk}^{T}E_{k}R_{k}^{-1}
  31.       γk=δk−1ρkbk\gamma_{k} = \delta_{k}^{-1}\rho_{k}b_{k}
  32.       H_(k)=(H(k−1)Ukγk−1e1eskT01,skHkγkesT)\underline{H}_{(k)} = \begin{pmatrix} H_{(k-1)} & U_{k} \\ \begin{matrix} \gamma_{k - 1}e_{1}e_{sk}^{T} \\ 0_{1,sk} \end{matrix} & \begin{matrix} H_{k} \\ \gamma_{k}e_{s}^{T} \end{matrix} \end{pmatrix}
  33.     endif\mathrm{endif}
  34.   end\mathrm{end}
  35.   fori=1,2,…,st\mathrm{for}\ i = 1,2,\ldots,st
  36.     fork=1,2,…,i−1\mathrm{for}\ k = 1,2,\ldots,i - 1
  37.       (hk,ihk+1,i)=(cos⁡ϕk−sin⁡ϕksin⁡ϕkcos⁡ϕk)(hk,ihk+1,i)\begin{pmatrix} h_{k,i} \\ h_{k + 1,i} \end{pmatrix} = \begin{pmatrix} \cos\phi_{k} & -\sin\phi_{k} \\ \sin\phi_{k} & \cos\phi_{k} \end{pmatrix}\begin{pmatrix} h_{k,i} \\ h_{k + 1,i} \end{pmatrix}
  38.     end\mathrm{end}
  39.     cos⁡ϕi=1/1+(hi+1,i/hi,i)2\cos\phi_{i} = 1\ /\ \sqrt{1 + (h_{i + 1,i}\ /\ h_{i,i})^{2}}
  40.     sin⁡ϕi=−cos⁡ϕihi+1,i/hi,i\sin\phi_{i} = -\cos\phi_{i}h_{i + 1,i}\ /\ h_{i,i}
  41.     (ζiζi+1)=(cos⁡ϕi−sin⁡ϕisin⁡ϕicos⁡ϕi)(ζiζi+1)\begin{pmatrix} \zeta_{i} \\ \zeta_{i + 1} \end{pmatrix} = \begin{pmatrix} \cos\phi_{i} & -\sin\phi_{i} \\ \sin\phi_{i} & \cos\phi_{i} \end{pmatrix}\begin{pmatrix} \zeta_{i} \\ \zeta_{i + 1} \end{pmatrix}
  42.     hi,i=cos⁡ϕihi,i−sin⁡ϕihi+1,ih_{i,i} = \cos\phi_{i}h_{i,i} - \sin\phi_{i}h_{i + 1,i}
  43.     hi+1,i=0h_{i + 1,i} = 0
  44.   end\mathrm{end}
  45.   y=H(t−1)−1ζ1:sty = H_{(t-1)}^{-1}\zeta_{1:st}
  46.   solvex̂fromKx̂=∑k=1stykqk\mathrm{solve}\ \hat{x}\ \mathrm{from}\ K\hat{x} = \sum_{k = 1}^{st} y_{k}q_{k}
  47.   x(j+1)=x(j)+x̂x^{(j+1)} = x^{(j)} + \hat{x}
  48. end\mathrm{end}

 14〜17 行目はkk番目のブロックの単項式基底 (B_\underline{B}は固定) を作り, 前処理と疎行列ベクトル積だけからなる (集団通信を含まない). 35〜44 行目はtt個のブロックぶんの Hessenberg 行列の各列に Givens 回転を施し, 45〜47 行目で解を更新する.

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

8.4.1 Q の作り方 (set_explicit_q)

 pcagmresは, 直交化した基底QQを陽に作るかどうかをset_explicit_q(mode)で選べる (get_explicit_q()で取得できる). modeは名前空間parcel::krylovの次の定数である.

定数 値 動作
CAGMRES_Q_AUTO (既定) 0 上のアルゴリズムのとおりQQを作る. ただしQR_CHOLESKYQRかつt=1t = 1のときだけQQを作らない
CAGMRES_Q_EXPLICIT 1 常にQQを作る (QR_CHOLESKYQRでt=1t = 1でも作る)
CAGMRES_Q_IMPLICIT 2 どのttでもQQを作らない (下記). 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のように示される.

8.4.2 Q を作らない場合 (CAGMRES_Q_IMPLICIT) [2,3,7]

 set_explicit_q(parcel::krylov::CAGMRES_Q_IMPLICIT)を指定した場合は, 上のアルゴリズムと次の 3 点が異なる.

  1. 正規直交基底QQを陽に作らない. 基底V=[v0,…,vst]V = [v_{0},\ldots,v_{st}]をそのまま保持し, Gram 行列VTVV^{T}Vの Cholesky 分解から上三角行列RR (V=QRV = QR) だけを求める. Hessenberg 行列は上のアルゴリズムと同じ式でRRから組み立て, 解の更新にはQyQyの代わりにV(R−1y)V(R^{-1}y)を用いる. 既定 (CAGMRES_Q_AUTO) のQR_CHOLESKYQRはt=1t = 1のときだけQQを省略するが, CAGMRES_Q_IMPLICITはt>1t > 1でも省略する.
  2. 基底を偶数番目と奇数番目に分けて格納し, それぞれの格納精度をsolver()のテンプレート引数Teven_basis・Todd_basisで選べる (既定はどちらもTbasis. CAGMRES_Q_IMPLICIT以外では使わない).
  3. set_qr_algo(parcel::qr::QR_CAGMRES_CHOLESKYQR)を指定すると, 最初のブロックの Gram 行列をモーメントから作る (QR分解の章). AAが対称で前処理なしの場合に限って正しい.

 x(0)x^{(0)}はsolver()の引数xに与えた初期値, x(j)x^{(j)}はjj回目のリスタートの開始時の近似解, KKはset_precon_algo()などで指定した前処理行列, ss・ttはset_restart(s, t)で指定する値 (既定s=8s = 8, t=4t = 4), toltolはset_tolerance() (既定 1.0e-8) の値である. リスタート回数の上限JJはset_max_iteration()の値NN (既定 10000) からJ=⌈N/(st)⌉J = \lceil N/(st) \rceilと決まる. この節では基底の番号を 0 から数え, Va:b=[va,…,vb]V_{a:b} = [v_{a},\ldots,v_{b}], Ra:b,c:dR_{a:b,c:d}はRRのaa〜bb行cc〜dd列の部分行列, Wk=Vsk+1:sk+sW_{k} = V_{sk+1:sk+s}はkk番目のブロックで新たに作るss本の基底, ele_{l}は第ll単位ベクトル (0 始まり) である. chol(S)\mathrm{chol}(S)は対称行列SSの Cholesky 分解S=UTUS = U^{T}Uの上三角行列UUを表す. H_(k)\underline{H}_{(k)}・ζ\zetaは上のpcagmresのアルゴリズムと同じであり, 28〜30 行目の Givens 回転は上のアルゴリズムの 35〜44 行目と同じ計算である.

  1. Chooseinitialguessx(0)\mathrm{Choose}\ \mathrm{initial}\ \mathrm{guess}\ x^{(0)}
  2. forj=0,1,…,J−1\mathrm{for}\ j = 0,1,\ldots,J - 1
  3.   r=b−Ax(j)r = b - Ax^{(j)}
  4.   if∥r∥/∥b∥<tolthen\mathrm{if}\ \|r\|\ /\ \|b\| < tol\ \mathrm{then}
  5.     quit\mathrm{quit}
  6.   endif\mathrm{endif}
  7.   v0=r/∥r∥v_{0} = r\ /\ \|r\|
  8.   ζ=(∥r∥,0,…,0)T\zeta = (\|r\|,0,\ldots,0)^{T}
  9.   fork=0,1,…,t−1\mathrm{for}\ k = 0,1,\ldots,t - 1
  10.     ifk=0then\mathrm{if}\ k = 0\ \mathrm{then}
  11.       v‾=v0\bar{v} = v_{0}
  12.     else\mathrm{else}
  13.       v‾=V0:skR0:sk,0:sk−1esk\bar{v} = V_{0:sk}R_{0:sk,0:sk}^{-1}e_{sk}
  14.     endif\mathrm{endif}
  15.     fori=1,2,…,s\mathrm{for}\ i = 1,2,\ldots,s
  16.       solvepfromKp=v‾\mathrm{solve}\ p\ \mathrm{from}\ Kp = \bar{v}
  17.       vsk+i=Apv_{sk + i} = Ap
  18.       v‾=vsk+i\bar{v} = v_{sk + i}
  19.     end\mathrm{end}
  20.     ifk=0then\mathrm{if}\ k = 0\ \mathrm{then}
  21.       R0:s,0:s=chol(V0:sTV0:s)R_{0:s,0:s} = \mathrm{chol}(V_{0:s}^{T}V_{0:s})
  22.     else\mathrm{else}
  23.       R0:sk,Wk=R0:sk,0:sk−T(V0:skTWk)R_{0:sk,W_{k}} = R_{0:sk,0:sk}^{-T}(V_{0:sk}^{T}W_{k})
  24.       RWk,Wk=chol(WkTWk−R0:sk,WkTR0:sk,Wk)R_{W_{k},W_{k}} = \mathrm{chol}(W_{k}^{T}W_{k} - R_{0:sk,W_{k}}^{T}R_{0:sk,W_{k}})
  25.     endif\mathrm{endif}
  26.     Computethek-thblockofH_(k)fromRasinpcagmres\mathrm{Compute}\ \mathrm{the}\ k\text{-}th\ \mathrm{block}\ \mathrm{of}\ \underline{H}_{(k)}\ \mathrm{from}\ R\ \mathrm{as}\ \mathrm{in}\ \mathrm{pcagmres}
  27.   end\mathrm{end}
  28.   foro=1,2,…,st\mathrm{for}\ o = 1,2,\ldots,st
  29.     applytheGivensrotationtocolumnoofH_(t−1)andζ\mathrm{apply}\ \mathrm{the}\ \mathrm{Givens}\ \mathrm{rotation}\ \mathrm{to}\ \mathrm{column}\ o\ \mathrm{of}\ \underline{H}_{(t-1)}\ \mathrm{and}\ \zeta
  30.   end\mathrm{end}
  31.   y=H(t−1)−1ζ1:sty = H_{(t-1)}^{-1}\zeta_{1:st}
  32.   z=R0:st−1,0:st−1−1yz = R_{0:st - 1,0:st - 1}^{-1}y
  33.   solvex̂fromKx̂=V0:st−1z\mathrm{solve}\ \hat{x}\ \mathrm{from}\ K\hat{x} = V_{0:st - 1}z
  34.   x(j+1)=x(j)+x̂x^{(j+1)} = x^{(j)} + \hat{x}
  35. end\mathrm{end}

 13 行目のv‾\bar{v}はQQの第sksk列qskq_{sk}であり, ブロックの始点だけをVVとRRから作る (上のアルゴリズムの 12 行目vsk+1=qsk+1v_{sk+1} = q_{sk+1}に当たる). 23 行目のR0:sk,Wk=Q0:skTWkR_{0:sk,W_{k}} = Q_{0:sk}^{T}W_{k}はブロック古典 Gram-Schmidt 法の係数, 24 行目は射影後のWkW_{k}の Cholesky QR であり, RRを上三角のまま 1 ブロックずつ延ばす. 26 行目では, k=0k = 0は上のアルゴリズムの 21〜22 行目, k>0k > 0は 28〜32 行目と同じ式で, C_k=[esk,R0:sk,Wk]\underline{C}_{k} = [e_{sk}, R_{0:sk,W_{k}}], Rk=RWk,WkR_{k} = R_{W_{k},W_{k}}として組み立てる. 31 行目のH(t−1)H_{(t-1)}は, 回転後のH_(t−1)\underline{H}_{(t-1)}から最終行を除いた上三角行列である.

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

8.5 直交化の精度と基底の精度

 GMRES 系のソルバは Krylov 部分空間の基底を直交化しながら反復する. pgmres・pcagmresでは, 基底を格納する精度と, 直交化を計算する精度を別々に指定できる (書式は使用方法の「線形ソルバの呼び出し」).

 本節では, nlocaln_{local}は局所行数, mmはpgmresのリスタート周期 (set_restart(m)) である. ssとttは CA-GMRES(s,t) (pcagmres) のパラメタで, set_restart(s, t)で指定する (既定s=8s = 8, t=4t = 4).

 丸め誤差があると, 直交化した基底QQは厳密には直交しない. 直交性の損失∥I−QTQ∥\|I - Q^{T}Q\|は, 直交化の計算に用いる精度の単位丸め誤差uuと, 直交化する前の基底VVの条件数κ(V)\kappa(V)で決まる. 修正 Gram-Schmidt 法ではuκ(V)u\,\kappa(V)に [8], 古典 Gram-Schmidt 法 [9] と Cholesky QR 法 [11] ではuκ(V)2u\,\kappa(V)^{2}に比例する. uuは倍精度で約1.1×10−161.1 \times 10^{-16}, 単精度で約6.0×10−86.0 \times 10^{-8}, 半精度で約4.9×10−44.9 \times 10^{-4}である. Cholesky QR 法は, uκ(V)2u\,\kappa(V)^{2}が 1 に近づくと Gram 行列が数値的に正定値でなくなり, 分解できない. また, 直交化したQQを低い精度で格納すると, その丸め (QQの各要素に相対uu程度) の分だけ直交性が損なわれる.

 pgmresの Arnoldi 過程は, 新しいベクトルを 1 本ずつ, それまでに直交化した基底に対して直交化する. 修正 Gram-Schmidt 法による GMRES は後退安定であり, 直交性が大きく失われるのは残差が十分小さくなってからである [10]. このため直交化の精度TGSを低精度にしても反復は進み, 影響は主に到達できる残差の下限として現れる (下限はuuとともに大きくなる).

 pcagmresでは, 直交化は 2 段に分かれ, ssとttがそれぞれに効く.

 基底の階数落ち (幸運な破綻) の判定には, u=max⁡(uTbasis,uTcalcQR)u = \max(u_{Tbasis}, u_{TcalcQR})から決めた閾値を用いる (Cholesky QR 法では100u100\sqrt{u}, それ以外は1000u1000u).

 各引数が受け持つ, 長さnlocaln_{local}のベクトルを扱う計算 (内積と更新) とその精度を次に示す. pcagmresでは, 直交基底QQを陽に作るかどうか (set_explicit_q(). 線形ソルバの章) でTcalcQR・THessenbergの役割が異なることに注意する.

ソルバ 引数 受け持つもの データの大きさ
pgmres Tvec (データ精度) 基底ベクトルの格納 nlocal×(m+1)n_{local} \times (m+1)
pgmres TGS Gram-Schmidt 直交化の内積と係数の計算 長さnlocaln_{local}の内積
pgmres THessenberg 最小二乗問題の解yy (ホストで解く) をデバイスに渡す精度 長さmm
pcagmres Tbasis 基底VVと直交化後の基底QQの格納 VVはnlocal×(s+1)n_{local} \times (s+1), QQはnlocal×(st+1)n_{local} \times (st+1)
pcagmres (QQを作る場合) TcalcQR ブロック内の QR 分解の計算 (長さnlocaln_{local}の内積) 長さnlocaln_{local}の内積
pcagmres (QQを作る場合) THessenberg ブロック間の射影QTVQ^{T}Vの計算 (長さnlocaln_{local}の内積) とVVからの差し引き, RR・射影係数・Hessenberg 行列の格納 長さnlocaln_{local}の内積, (st+1)(s+1)(st+1)(s+1)
pcagmres (CAGMRES_Q_IMPLICIT) TcalcQR Gram 行列の計算 (ブロック内とブロック間の長さnlocaln_{local}の内積のすべて) 長さnlocaln_{local}の内積
pcagmres (CAGMRES_Q_IMPLICIT) THessenberg Gram 行列・RR・Hessenberg 行列の格納 (st+1)(s+1)(st+1)(s+1)程度
pcagmres (CAGMRES_Q_IMPLICIT) Todd_basis, Teven_basis 基底VVの奇数番目・偶数番目の格納 合わせてnlocal×(st+1)n_{local} \times (st+1)

 サンプルがTcalcQR・THessenbergを倍精度に固定する理由は次のとおりである. 精度を下げてメモリ量とデータ移動量が減るのは, 長さnlocaln_{local}のベクトルをst+1st+1本以上持つ基底 (Tbasis) である. 一方, 直交化の成否を決めるのは, ブロック内とブロック間の直交化の計算精度 (pcagmresではTcalcQRとTHessenberg, QQを作らない方式CAGMRES_Q_IMPLICITではTcalcQR) である. これらは基底を読みながら内積を累積する精度であり, 上げても読み書きする基底のデータの量は変わらない. 格納する行列 (RR・Hessenberg 行列など) は(st+1)(s+1)(st+1)(s+1)程度と小さい. このため, 基底だけをデータ精度に合わせて下げ, 直交化の計算と小さな行列は倍精度に保つという使い分けになる. このとき直交性は, 基底QQを格納する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 (QQを作らない方式を含む) のTcalcQR・THessenbergを倍精度とする. これらを下げた場合の収束は確かめていない.