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

11 QR分解

 本ライブラリルーチンで用いるQR分解 (ベクトル群の直交化) のアルゴリズムについて説明する. 線形ソルバでは set_qr_algo() で次の定数を指定して選ぶ. 記号の約束は線形ソルバの章の冒頭に示したとおりである.

定数 方式 利用できるソルバ
parcel::qr::QR_CGS (0) 古典 Gram-Schmidt 法 pgmres, pcagmres (CAGMRES_Q_IMPLICIT以外)
parcel::qr::QR_MGS (1) 修正 Gram-Schmidt 法 pgmres, pcagmres (CAGMRES_Q_IMPLICIT以外)
parcel::qr::QR_CHOLESKYQR (2) Cholesky QR 法 pcagmres
parcel::qr::QR_CAGMRES_CHOLESKYQR (202) モーメント法による Cholesky QR 法 (対称行列・前処理なし専用) pcagmres (CAGMRES_Q_IMPLICITのときだけ)

 ソルバが対応しない値をset_qr_algo()に与えるとstd::invalid_argumentを投げる. pcagmresのQQの作り方 (set_explicit_q()) との組合せはsolver()の入口で検査する (線形ソルバの章).

 古典 Gram-Schmidt 法を 2 回繰り返す CGS2 は, Krylov-Schur 法 (ks_arnoldi) の Arnoldi 過程の中で用いる (ks_arnoldiではset_qr_algo(parcel::qr::QR_CGS)が CGS2 を表し, これが既定. pgmres・pcagmresのQR_CGSは 1 回だけ適用する古典 Gram-Schmidt 法で, この 2 つのソルバでは CGS2 を選べない). 以下のアルゴリズムでは, pp本のベクトルを並べたV=[v1,…,vp]V = [v_1, \ldots, v_p]を直交化して, 列qiq_iからなるQQと上三角行列RR (要素Rk,iR_{k,i}) を得る.


11.1 古典 Gram-Schmidt 法[1]

 Gram-Schmidt の直交化によるQR分解. 第 ii 列に対する内積をまとめて計算できるため集団通信が少なく並列性は高いが, 直交性の誤差は行列の条件数の 2 乗に比例して悪化する. QR_CGS は再直交化を行わない (1 回のみ).

  1. fori=1,…,p\mathrm{for}\ i = 1,\ldots,p
  2.   fork=1,…,i−1\mathrm{for}\ k = 1,\ldots,i - 1
  3.     Rk,i=⟨qk,vi⟩R_{k,i} = \langle q_{k},v_{i} \rangle
  4.   end\mathrm{end}
  5.   fork=1,…,i−1\mathrm{for}\ k = 1,\ldots,i - 1
  6.     vi=vi−Rk,iqkv_{i} = v_{i} - R_{k,i}q_{k}
  7.   end\mathrm{end}
  8.   Ri,i=∥vi∥R_{i,i} = \|v_{i}\|
  9.   qi=vi/Ri,iq_{i} = v_{i}\ /\ R_{i,i}
  10. end\mathrm{end}


11.2 修正 Gram-Schmidt 法[1]

 誤差の低減を目的に古典 Gram-Schmidt 法のアルゴリズムを修正したQR分解. 直交化済みの成分を 1 本ずつ差し引いてから次の内積を計算するため, 古典 Gram-Schmidt 法よりも直交性が高いが, 内積ごとに集団通信が必要になる.

  1. fori=1,…,p\mathrm{for}\ i = 1,\ldots,p
  2.   fork=1,…,i−1\mathrm{for}\ k = 1,\ldots,i - 1
  3.     Rk,i=⟨qk,vi⟩R_{k,i} = \langle q_{k},v_{i} \rangle
  4.     vi=vi−Rk,iqkv_{i} = v_{i} - R_{k,i}q_{k}
  5.   end\mathrm{end}
  6.   Ri,i=∥vi∥R_{i,i} = \|v_{i}\|
  7.   qi=vi/Ri,iq_{i} = v_{i}\ /\ R_{i,i}
  8. end\mathrm{end}


11.3 再直交化付き古典 Gram-Schmidt 法 (CGS2)[6]

 古典 Gram-Schmidt 法の直交化をもう一度繰り返す方法である. 1 回目で丸め誤差により残ったq1,…,qi−1q_1, \ldots, q_{i-1}方向の成分を 2 回目で取り除くため, VV の数値的な階数が落ちていない限り, 直交性の誤差はマシン精度程度に保たれる (twice is enough). 内積と更新の演算量は古典 Gram-Schmidt 法の 2 倍になるが, 各回の内積はまとめて計算できるので, 集団通信は 1 列あたり 2 回で済む. 修正 Gram-Schmidt 法の i−1i - 1 回より少ない.

 Krylov-Schur 法 (ks_arnoldi) の Arnoldi 過程は既定でこの方法を用いる. 各 Arnoldi ステップで新しい基底ベクトルを既存の基底に対して直交化する. Krylov-Schur 法はリスタートを重ねても基底の直交性が保たれていることを前提にしており, 直交性が失われると, 重複した固有値に対して偽の固有値 (ghost eigenvalue) が現れる. CGS2 はこれを防ぐ.

  1. R1:i−1,i=0R_{1:i - 1,i} = 0
  2. forpass=1,2\mathrm{for}\ pass = 1,2
  3.   ξ=Q1:i−1Tvi\xi = Q_{1:i - 1}^{T}v_{i}
  4.   vi=vi−Q1:i−1ξv_{i} = v_{i} - Q_{1:i - 1}\xi
  5.   R1:i−1,i=R1:i−1,i+ξR_{1:i - 1,i} = R_{1:i - 1,i} + \xi
  6. end\mathrm{end}
  7. Ri,i=∥vi∥R_{i,i} = \|v_{i}\|
  8. qi=vi/Ri,iq_{i} = v_{i}\ /\ R_{i,i}


11.4 Cholesky QR 法[7]

 Cholesky QR は行列積と Cholesky 分解で構成されるQR分解である. 演算密度が高く 1 回の集団通信で計算できるが, 直交性の誤差は行列の条件数の 2 乗に比例して悪化する. PARCEL は 1 回だけ行う方式であり, 繰り返す方式 (CholeskyQR2) は実装していない. Gram 行列はデバイス上で計算し, Cholesky 分解はホスト上で行う.

  1. G=VTVG = V^{T}V
  2. ComputeRfromG=RTR(Choleskydecomposition)\mathrm{Compute}\ R\ \mathrm{from}\ G = R^{T}R\ (\mathrm{Cholesky}\ \mathrm{decomposition})
  3. Q=VR−1Q = VR^{-1}



11.5 モーメント法による Cholesky QR 法 (QR_CAGMRES_CHOLESKYQR)

 pcagmresでQQを作らない場合 (CAGMRES_Q_IMPLICIT. 線形ソルバの章) の最初のブロック (k=0k = 0) だけで用いる, CA-GMRES 専用の Cholesky QR 法である. 前処理なしの単項式基底vi=Aiv0v_{i} = A^{i}v_{0} (i=0,…,si = 0,\ldots,s) では, AAが対称なら⟨vi,vj⟩=v0TAi+jv0=μi+j\langle v_{i},v_{j} \rangle = v_{0}^{T}A^{i+j}v_{0} = \mu_{i+j} (モーメント) となり, Gram 行列G=VTVG = V^{T}Vは Hankel 行列 (Gij=μi+jG_{ij} = \mu_{i+j}) である. μ0,…,μ2s\mu_{0},\ldots,\mu_{2s}は, 4 本[v0,v1,vs−1,vs][v_{0},v_{1},v_{s-1},v_{s}]と偶数番目の基底[v0,v2,…,vs][v_{0},v_{2},\ldots,v_{s}]の内積4×(s/2+1)4 \times (s/2+1)個から得られるので, (s+1)2(s+1)^{2}個の内積を計算しなくてよい. QQは作らず, RRだけを返す.

 V=[v0,…,vs]V = [v_{0},\ldots,v_{s}] (ssは 2 以上の偶数) である.

  1. C=[v0,v1,vs−1,vs]T[v0,v2,…,vs]C = [v_{0},v_{1},v_{s-1},v_{s}]^{T}[v_{0},v_{2},\ldots,v_{s}]
  2. Setμ0,…,μ2sfromC\mathrm{Set}\ \mu_{0},\ldots,\mu_{2s}\ \mathrm{from}\ C
  3. Gij=μi+j(0≤i,j≤s)G_{ij} = \mu_{i+j}\ \ (0 \leq i,j \leq s)
  4. ComputeRfromG=RTR(Choleskydecomposition)\mathrm{Compute}\ R\ \mathrm{from}\ G = R^{T}R\ (\mathrm{Cholesky}\ \mathrm{decomposition})

 1 行目の行列積はデバイス上で行い, MPI 並列時は局所の値を集約する (集団通信 1 回). Cholesky 分解はホスト上で行う. AAが対称でない場合や前処理を施した基底ではGGが Hankel 行列にならず, 誤ったRRとなる. pcagmresは前処理なしとssが偶数であることを入口で検査するが, AAの対称性は検査しない.