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

1 共通事項

 本書は PARCEL の API を言語ごとの章に分けて示す. 言語によらない事項 (ソルバ, 入力の行列, 設定の意味と既定値, 定数, 結果の意味, 収束状態, MPI での扱い) は本章と次章「ソルバごとの収束判定」にまとめ, 各言語の章にはその言語での名前と書き方, エラーの知らせ方, 例を示す. 利用者は本章・次章と, 使う言語の章を読めばよい. 言語はページの上のタブで切り替える.

言語 章
C++ SYCL版PARCELクラス から parcel::krylov::ks_arnoldi まで
C言語 C言語の API
Fortran Fortran の API
Python Python の API

 各言語の章の冒頭に, 本章の設定・定数・結果とその言語での名前の対応表を置く.

1.1 各項目の書式

 各言語の章の関数・型の項目は, 次の欄からなる. 該当しない欄は省く.

欄 内容
概要 関数の働き
書式 その言語での宣言
引数 名前, 入出力 (入力 / 出力 / 入出力), 型, 説明, 既定値. 既定値は指定しなかったときにライブラリが使う値である
前提条件 引数の有効範囲と, 外れたときの動作. ライブラリが検査しない場合は「検査しない」と書く
戻り値 戻り値の意味
MPI 集団操作かどうか, 全ランクで同じ値を与える必要があるか
注意 使い方の注意
関連項目 関係する関数と章
例 呼び出し例

1.2 ソルバ

 PARCEL は次の 7 つのソルバを持つ. ソルバの名前は全言語で共通である. アルゴリズムは利用者ガイドの線形ソルバの章と固有値ソルバの章に, 選び方はソルバの選び方に示す.

ソルバ 方法 解く問題
pcg 前処理付き共役勾配法 Ax=bAx = b. AAと前処理行列KKが対称正定値
pbicgstab 前処理付き安定化双共役勾配法 Ax=bAx = b (非対称行列)
pgmres 前処理付き一般化最小残差法 (右前処理, リスタート付き) Ax=bAx = b (非対称行列)
pcagmres 前処理付き通信削減型一般化最小残差法 (CA-GMRES). ss本の基底をまとめて作り, QR 分解で直交化する Ax=bAx = b (非対称行列)
power べき乗法 AAの絶対値最大の固有対 1 組
inverse_power 逆べき乗法. 各反復で内部の線形ソルバがAy=xAy = xを解く AAの絶対値最小の固有対 1 組
ks_arnoldi Arnoldi 過程と Krylov-Schur リスタート. 非対称行列, 複素共役対の固有値にも対応する AAの絶対値の大きい側の複数の固有対. shift-invert ではシフトσ\sigmaに近い固有対

 固有値ソルバは標準固有値問題Ax=λxAx = \lambda xを扱う. 前処理後の行列のスペクトルを選ぶと, AAの代わりにAK−1AK^{-1}の固有値を求める. ソルバはビルドから外せる (利用者ガイドの「ビルドするソルバの取捨」). 外したソルバを呼んだ場合の扱いは各言語の章に示す.

1.3 記号と用語

 本書では次の記号と用語を用いる.

記号・用語 意味
nlocaln_{local} 各ランクの担当行数
nglobaln_{global} 全ランクのnlocaln_{local}の和 (行列の行数)
toltol 収束判定値
NN 最大反復回数
mm pgmres のリスタート周期, ks_arnoldi の Krylov 部分空間の最大次元
ss, tt pcagmres の 1 回の基底生成で作るベクトル数と, リスタートまでの基底生成回数 (設定)
kkeepk_{keep}, nevnev ks_arnoldi がリスタート後に残す (最後に返す) 固有対の数と, 収束判定の対象とする固有対の数 (設定)
NRN_{R} ks_arnoldi の最大リスタート回数
KK, KinK_{in} 前処理行列 (前処理の設定でAAから作る) と, 固有値ソルバの内部線形ソルバの前処理行列
shift-invert シフトσ\sigmaの近くの固有値を求める方法. (A−σI)−1(A - \sigma I)^{-1}の絶対値の大きい固有値θ\thetaを求め, λ=σ+1/θ\lambda = \sigma + 1/\thetaに戻す
Op\mathrm{Op} ks_arnoldi が Arnoldi 過程を適用する演算子. AA, AK−1AK^{-1} (前処理後の行列のスペクトルを求める場合), shift-invert では(A−σI)−1(A - \sigma I)^{-1}または(AK−1−σI)−1(AK^{-1} - \sigma I)^{-1}
Ritz 対(θ,x)(\theta, x) Krylov 部分空間の中で求めたOp\mathrm{Op}の近似固有値θ\thetaと近似固有ベクトルxx
真の残差 解xxから計算し直した相対残差∥b−Ax∥/∥b∥\|b - Ax\| / \|b\|. これに対し, 反復の漸化式で更新した残差を漸化式の残差と呼ぶ
幸運な破綻 Krylov 部分空間が不変部分空間になり, 次の基底ベクトルを作れなくなること. 解 (固有対) はその部分空間に含まれるので, それ自体は失敗ではない
rank 0 コミュニケータでの番号が 0 のランク. 途中経過と結果を標準出力に書く

1.4 入力の行列

 係数行列は CRS 形式で与える. MPI で並列に解く場合は, 各ランクが連続した行のブロック (大域行番号nstartnstartからnlocaln_{local}行) を受け持ち, その行の部分だけを渡す. 形式の説明は利用者ガイドのデータ構造の節に示す.

 次の条件はライブラリが検査し, 満たさなければ全ランクが同じエラーになる (エラーの知らせ方は各言語の章).

 次の条件は検査しないので, 満たさないと誤った結果を黙って返しうる.

 MPI なしのビルドでは 1 プロセスが行列の全体を持つ (担当行は全行).

1.5 設定

 ソルバの動作は次の設定で決まる. 指定しなかった設定は表の既定値になる. 各言語での名前は各言語の章の対応表に示す. 取りうる値を外れた値は受け付けない (エラーになる). 設定は全ランクで同じ値を与える.

設定 使うソルバ 意味 取りうる値 既定値
収束判定値 toltol 全ソルバ 線形ソルバでは相対残差∥r∥/∥b∥\|r\|/\|b\|, power・inverse_power では固有値の相対変化, ks_arnoldi では Ritz 対(θ,x)(\theta, x)の相対残差∥Opx−θx∥/(|θ|∥x∥)\|\mathrm{Op}\,x-\theta x\|/(|\theta|\|x\|)に対する判定値 (shift-invert でもλ\lambdaに戻す前のθ\thetaで判定する) 有限の正の数 1.0e-8
最大反復回数 NN 線形ソルバ, power, inverse_power 反復回数の上限. pgmres・pcagmres では内側反復の総数, power・inverse_power では外側反復の回数. ks_arnoldi は使わない (最大リスタート回数を使う) 1 以上. pgmres・pcagmres でもmm (stst) の倍数でなくてよい 10000
前処理の種類 全ソルバ 前処理行列KKの種類 (定数). 線形ソルバでは反復の前処理, 固有値ソルバでは前処理後の行列のスペクトルを求める場合のKK なし, ポイント Jacobi, ブロック Jacobi, Jacobi なし
Jacobi 前処理の反復回数 前処理が Jacobi のとき Jacobi 反復の回数 1 以上 1
ブロック Jacobi 前処理のブロック数 前処理がブロック Jacobi のとき ランクあたりのブロック数. 適用の並列度に等しい. 細かくするほど前処理は弱くなる 1 以上で担当行数以下 (担当行数以下であることは検査しない) 自動. CPU では環境変数PARCEL_NBLOCK, それが無ければ OpenMP のスレッド数, どちらも得られなければビルド時の値. GPU では 1 ブロック 2 行
前処理行列・前処理ベクトルのスケーリング 前処理がブロック Jacobi・Jacobi のとき 行列・残差を最大値で割って半精度の表現範囲に収める処理の有無 (行列とベクトルで別に指定する) 有, 無, 自動 自動 (ブロック Jacobi では有. それ以外は前処理の演算精度または前処理行列の精度が半精度のときだけ有)
リスタート周期 mm pgmres 基底ベクトルm+1m + 1本ぶんの領域を確保する 1 以上 30
直交化の方式 pgmres Arnoldi 過程の直交化 (定数) 古典 Gram-Schmidt, 修正 Gram-Schmidt 修正 Gram-Schmidt
基底生成の大きさ ss, tt pcagmres 1 回の基底生成で作るベクトル数ssと, リスタートまでの基底生成回数tt. リスタート周期はs×ts \times t いずれも 1 以上 s=8s = 8, t=4t = 4
QR 分解の方式 pcagmres 基底の QR 分解 (定数, 組合せの規則) 古典 Gram-Schmidt, 修正 Gram-Schmidt, Cholesky QR, モーメント法による Cholesky QR 修正 Gram-Schmidt (QQを作らない場合は Cholesky QR)
QQの作り方 pcagmres 正規直交基底QQを陽に作るかどうか (定数, 組合せの規則) AUTO, EXPLICIT, IMPLICIT AUTO
前処理後の行列のスペクトル 固有値ソルバ 偽のときAAの固有値を求め, 外側の固有値反復は前処理を使わない. 真のときAK−1AK^{-1}の固有値を求める (補足) 真, 偽 偽
内部線形ソルバの種類 inverse_power 内部の線形ソルバ (定数). pcg はAAが対称 (正定値または負定値) の場合に限る (検査しない). 前処理後の行列のスペクトルを求める場合は種類によらず pgmres を使う pgmres, pcg pgmres
内部線形ソルバの収束判定値 inverse_power, ks_arnoldi の shift-invert 内部線形ソルバの相対残差の判定値 有限の正の数 1.0e-10
内部線形ソルバの最大反復回数 同上 内部線形ソルバの反復回数の上限 (pgmres では内側反復の総数. リスタート周期の倍数でなくてよい) 1 以上 inverse_power 5000, ks_arnoldi 2000
内部線形ソルバのリスタート周期 同上 内部 pgmres のリスタート周期. 内部が pcg のときは使わない 1 以上 30
内部線形ソルバの前処理 同上 内部線形ソルバの前処理KinK_{in}の種類, Jacobi 前処理の反復回数, ブロック Jacobi 前処理のブロック数, スケーリング (補足) 前処理の種類, 反復回数, ブロック数, スケーリングと同じ Jacobi (反復 1 回), ブロック数・スケーリングは自動
shift-invert ks_arnoldi 有効にするとσ\sigmaに近い固有値を求める. 値はシフトσ\sigma 任意の実数. σ\sigmaが固有値に一致しないこと (検査しない) 無効
Krylov 部分空間の大きさ mm, kkeepk_{keep}, nevnev ks_arnoldi 部分空間の最大次元mm, リスタート後に残す (最後に返す) 固有対の数kkeepk_{keep}, 収束判定の対象とする固有対の数nevnev 1≤nev≤kkeep<m≤nglobal1 \leq nev \leq k_{keep} < m \leq n_{global} m=30m = 30, kkeep=10k_{keep} = 10, nev=4nev = 4
最大リスタート回数 NRN_{R} ks_arnoldi リスタートの回数の上限 1 以上 200
直交化の方式 (ks_arnoldi) ks_arnoldi Arnoldi 過程の直交化 (定数). どちらも 2 回適用する (古典 Gram-Schmidt 法 2 回 = CGS2, 修正 Gram-Schmidt 法 2 回 = MGS2). 固有値の精度は同等で, 速さだけが違う 古典 Gram-Schmidt, 修正 Gram-Schmidt 古典 Gram-Schmidt (CGS2). ライブラリのビルド時の指定で修正 Gram-Schmidt にできる
初期ベクトル ks_arnoldi Arnoldi 過程の初期ベクトル. power・inverse_power は常に既定のベクトルを使う 任意のベクトル. ノルムが 0 または非有限なら既定のベクトルに置き換える (rank 0 がその旨を表示する) 大域行番号から作るベクトル (行分割によらない)

 設定によっては, 言語によって指定できないものや, 表と異なる表し方をするもの (例えば「既定値を使う」を 0 で表す) がある. それらは各言語の章の対応表に示す.

1.5.1 前処理の補足

1.5.2 固有値ソルバの補足

1.5.3 pcagmres のQQの作り方と QR 分解

 QQの作り方 (定数) は次のとおりである.

作り方 動作
AUTO QR 分解が Cholesky QR かつt=1t = 1のときだけQQを作らず, それ以外はQQを作る
EXPLICIT 常にQQを作る (Cholesky QR でt=1t = 1でも作る)
IMPLICIT どのttでもQQを作らない. 基底VVの Gram 行列の Cholesky 分解からRRだけを求め, 解の更新にV(R−1y)V(R^{-1}y)を用いる. QR 分解は Cholesky QR またはモーメント法による Cholesky QR に限る

 QQの作り方と QR 分解の組合せは, 設定を与える順序によらないよう求解の入口で検査し, 次の場合は受け付けない (全ランクで同じ判定).

 モーメント法による Cholesky QR (モーメント法) はAAが対称の場合に限る. これは検査せず, 非対称なAAでは誤ったRRを用いて誤った結果を返す. AUTO と EXPLICIT は, t=1t = 1の Cholesky QR 以外では同じ計算を行う. IMPLICIT は計算の順序が異なるので, 同じss, ttと QR 分解でも結果は丸め誤差の範囲で異なる. IMPLICIT では Cholesky QR 法の直交性の誤差が基底の条件数の 2 乗に比例するので, ssを大きくすると収束が悪化しうる. FP16 のデータ精度・計算精度では, Cholesky QR 系 (IMPLICIT とモーメント法) を使わない (ss, ttによらず NaN または未収束になる. 検査はしない). 方法は利用者ガイドの線形ソルバの章と QR分解の章に示す.

1.6 定数

 設定に与える値は次の定数で表す. 値は全言語で同じであり, 各言語での名前は各言語の章に示す.

 前処理の種類:

定数 値 前処理
NONE 0 前処理なし
POINTJACOBI 1 ポイント Jacobi 前処理
BLOCKJACOBI 2 ブロック Jacobi 前処理
JACOBI 4 Jacobi 前処理

 直交化・QR 分解の方式:

定数 値 方式 使えるソルバ
CGS 0 古典 Gram-Schmidt 法 pgmres, pcagmres (QQを作る場合), ks_arnoldi (2 回適用する)
MGS 1 修正 Gram-Schmidt 法 pgmres, pcagmres (QQを作る場合), ks_arnoldi (2 回適用する)
CHOLESKYQR 2 Cholesky QR 法 pcagmres
CAGMRES_CHOLESKYQR 202 モーメント法による Cholesky QR 法 (対称行列・前処理なし専用) pcagmres (IMPLICIT のときだけ)

 内部線形ソルバの種類:

定数 値 ソルバ
PGMRES 0 右前処理 pgmres
PCG 1 pcg

 pcagmres のQQの作り方:

定数 値 動作
AUTO 0 上記
EXPLICIT 1 同上
IMPLICIT 2 同上

 収束状態の定数は次節に示す.

1.7 結果

 求解は解 (固有値ソルバでは固有値と固有ベクトル) のほか, 次の値を返す. 値は全ランクで同じである. 意味の詳細はソルバごとに異なり, 収束状態の節と次章に示す.

結果 意味
収束状態 収束状態の定数のいずれか. 正は収束, 負は失敗, 0 は求解を実行していない
反復回数 数え方はソルバごとに異なる (下表)
残差 収束判定値と比べた相対値 (下表). 計算していなければ NaN
真の残差 線形ソルバの終了時に計算した∥b−Ax∥/∥b∥\|b - Ax\|/\|b\|. 追加の計算をせずに返す. 固有値ソルバでは NaN. pcg・pbicgstab の残差は漸化式の残差なので, 丸め誤差により真の残差と離れることがある. 解の精度を確かめる場合はこちらを見る
収束した固有対の数 ks_arnoldi の最後の収束判定で, nevnev個のうち判定値を満たした固有対の数 (NaN は数えない. 不変部分空間などで真の残差を確かめた場合はその数). 収束時はnevnev. 他のソルバでは 0
内部線形ソルバの失敗回数 inverse_power と ks_arnoldi の shift-invert で, 内部線形ソルバが収束判定値を満たさずに終わった回数. power とシフトなしの ks_arnoldi では 0. 外側の収束状態には反映しない. 0 でない場合は内部線形ソルバの最大反復回数や前処理を見直す

1.7.1 固有値と固有ベクトルの出力

1.8 収束状態

 求解が返す収束状態は次の定数である (PETSc のKSPConvergedReasonに倣い, 正は収束, 負は失敗).

定数 値 意味
CONVERGED_RTOL 1 収束判定値を満たした
ITERATING 0 未実行 (求解を実行する前, または引数の誤りで解かなかった)
DIVERGED_ITS -1 最大反復回数 (ks_arnoldi は最大リスタート回数) に達した
DIVERGED_NANORINF -2 判定に用いる残差または固有値の推定値に NaN / Inf が現れた
DIVERGED_BREAKDOWN -3 アルゴリズムの破綻 (下表)

 各状態が起こる場合をソルバごとに示す. 詳細は次章に示す.

ソルバ CONVERGED_RTOL DIVERGED_NANORINF DIVERGED_BREAKDOWN
pcg 漸化式の相対残差 <tol< tol. ∥b∥=0\|b\| = 0 (反復せずにx=0x = 0, 反復回数 0). 初期残差の相対残差 <tol< tol (反復せずにxxは初期値のまま, 反復回数 0) 漸化式の相対残差が非有限になった時点で打ち切り 起こらない (ゼロ割りは検出せず, 結果が非有限なら NANORINF)
pbicgstab pcg と同じ. v=Aê=0v = A\hat{e} = 0で打ち切り, ∥e∥/∥b∥<tol\|e\|/\|b\| < tolの場合 (幸運な破綻) pcg と同じ ⟨r*,q⟩\langle r^{\ast},q \rangleが 0 または非有限, ω=0\omega = 0, ρ=0\rho = 0, v=0v = 0で∥e∥/∥b∥≥tol\|e\|/\|b\| \geq tol
pgmres リスタート先頭の真の相対残差 <tol< tol, または反復上限で終えたときの終了時の真の相対残差 <tol< tol. ∥b∥=0\|b\| = 0 真の相対残差, または Arnoldi 過程のhhが非有限になった時点で打ち切り 幸運な破綻で, 更新に使える列が無い (1 列目でHHが特異)
pcagmres pgmres と同じ 真の相対残差が非有限になった時点で打ち切り 幸運な破綻 (RRの階数落ち, hi+1,i≈0h_{i+1,i} \approx 0) の後, 更新に使える列が無い
power, inverse_power 固有値の相対変化 <tol< tol 固有値の推定値, 相対変化, または判定に用いる内積が非有限になった時点で打ち切り (inverse_power は内部線形ソルバが NANORINF で終わった場合も) power はAK−1x=0AK^{-1}x = 0, inverse_power は内部線形ソルバの解が 0
ks_arnoldi 判定対象nevnev個の Ritz 残差推定 ≤tol\leq tol (不変部分空間または乱数方向を含む場合は真の残差でも確認) Arnoldi 過程の値, Ritz 値, 残差推定が非有限になった時点で打ち切り 不変部分空間で真の残差を確かめられない, 有効次元がnevnev未満, LAPACK の失敗

 DIVERGED_ITS は, 上のいずれにも当たらずに最大反復回数 (ks_arnoldi は最大リスタート回数) に達した場合である. アルゴリズムの説明は利用者ガイドの線形ソルバの章と固有値ソルバの章に示す.

1.8.1 反復回数と残差の意味

 反復回数, 残差, 真の残差の意味はソルバごとに次のとおりである.

ソルバ 反復回数 残差 真の残差
pcg, pbicgstab 反復回数 漸化式の相対残差∥r∥/∥b∥\|r\|/\|b\| (pbicgstab のv=0v = 0での打ち切りでは∥e∥/∥b∥\|e\|/\|b\|) 終了時に計算した真の相対残差
pgmres 内側反復の総数 (リスタート回数 ×mm. 反復上限に達した場合は最大反復回数) リスタートの先頭で計算する真の相対残差. 反復上限で終わった場合は最後の更新後の値 (= 真の残差) 同左
pcagmres 基底ベクトルの総数 (周回数 ×s×ts \times t. 反復上限に達した場合は最大反復回数) pgmres と同じ 同左
power, inverse_power 外側反復の回数 固有値の相対変化|λ(i)−λ(i−1)|/|λ(i)||\lambda^{(i)} - \lambda^{(i-1)}|/|\lambda^{(i)}|. 非有限で打ち切った場合は NaN NaN
ks_arnoldi 実行したリスタートの回数 判定対象nevnev個の Ritz 残差推定の最大値 (真の残差で確かめた場合はその最大値) NaN

1.8.2 線形ソルバに共通の扱い

 線形ソルバ (pcg, pbicgstab, pgmres, pcagmres) では, ∥b∥=0\|b\| = 0の場合は反復せずにx=0x = 0を返し, 収束状態は CONVERGED_RTOL (反復回数 0, 残差・真の残差は 0) とする. rank 0 は||b|| = 0 : x = 0の行を書く.

 初期値x(0)x^{(0)}による初期残差の相対残差∥b−Ax(0)∥/∥b∥\|b - Ax^{(0)}\| / \|b\|がtoltol未満の場合 (x(0)x^{(0)}がすでに解である場合を含む) は, どの線形ソルバも反復せずに CONVERGED_RTOL (反復回数 0) を返し, xxは初期値のまま変えない. 残差と真の残差はこの初期残差の相対残差である.

1.8.3 標準出力

 rank 0 は求解の最後に次の形式の 1 行を標準出力に書く (非有限値はn/a). inverse_power は, linsolve_failures = ...を, ks_arnoldi は, ks_nconv = 収束数/nev (shift-invert ではlinsolve_failuresも) を加える.

 例: converged_reason = 1 (CONVERGED_RTOL) , its = 27 , residual = 4.200000e-10 , true_residual = 4.211375e-10

 このほか rank 0 は, 反復の途中経過と計算時間の内訳を書く. 線形ソルバは終了時の真の相対残差をfinish : residual true normの行に書く. pcagmres は反復の前の判定で戻る場合はこの行を書かない. 標準出力の書式は API に含めない. プログラムから結果を得る場合は各言語の結果の取得方法を用いる.

1.9 設定の扱いと MPI

1.10 精度

 PARCEL は, データを保持する精度 (データ精度) と演算の精度 (計算精度) を, 演算 (SpMV, 前処理, ベクトル演算, 内積) とデータ (行列, ベクトル, 前処理行列など) ごとに選べる. 型は半精度 (FP16), 単精度, 倍精度, long double, double-double (4倍精度相当) である. 精度の選び方は言語によって異なる.

言語 精度の指定
C++ 演算ごと・データごとにテンプレート引数で選ぶ (PARCELデータ型)
C言語・Fortran ラッパのコンパイル時のマクロで決まり, 実行時には変えられない (既定はすべて倍精度). 入出力の配列は倍精度
Python 倍精度だけ

 半精度を使う構成では, 精度で届く相対残差に下限があり, それより小さい収束判定値では停滞するか NaN で破綻する. 制約の詳細は利用者ガイドの使用方法の章の「精度の指定」と「数値精度と再現性」に示す.