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: (202) |
モーメント法による Cholesky QR 法 (対称行列・前処理なし専用) | pcagmres (CAGMRES_Q_IMPLICITのときだけ) |
ソルバが対応しない値をset_qr_algo()に与えるとstd::invalid_argumentを投げる. pcagmresのの作り方 (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 を選べない). 以下のアルゴリズムでは, 本のベクトルを並べたを直交化して, 列からなると上三角行列 (要素) を得る.
11.1 古典 Gram-Schmidt 法[1]
Gram-Schmidt の直交化によるQR分解. 第 列に対する内積をまとめて計算できるため集団通信が少なく並列性は高いが, 直交性の誤差は行列の条件数の 2 乗に比例して悪化する. QR_CGS は再直交化を行わない (1 回のみ).
- アルゴリズム
11.2 修正 Gram-Schmidt 法[1]
誤差の低減を目的に古典 Gram-Schmidt 法のアルゴリズムを修正したQR分解. 直交化済みの成分を 1 本ずつ差し引いてから次の内積を計算するため, 古典 Gram-Schmidt 法よりも直交性が高いが, 内積ごとに集団通信が必要になる.
- アルゴリズム
11.3 再直交化付き古典 Gram-Schmidt 法 (CGS2)[6]
古典 Gram-Schmidt 法の直交化をもう一度繰り返す方法である. 1 回目で丸め誤差により残った方向の成分を 2 回目で取り除くため, の数値的な階数が落ちていない限り, 直交性の誤差はマシン精度程度に保たれる (twice is enough). 内積と更新の演算量は古典 Gram-Schmidt 法の 2 倍になるが, 各回の内積はまとめて計算できるので, 集団通信は 1 列あたり 2 回で済む. 修正 Gram-Schmidt 法の 回より少ない.
Krylov-Schur 法 (ks_arnoldi) の Arnoldi 過程は既定でこの方法を用いる. 各 Arnoldi ステップで新しい基底ベクトルを既存の基底に対して直交化する. Krylov-Schur 法はリスタートを重ねても基底の直交性が保たれていることを前提にしており, 直交性が失われると, 重複した固有値に対して偽の固有値 (ghost eigenvalue) が現れる. CGS2 はこれを防ぐ.
- アルゴリズム (第 列)
11.4 Cholesky QR 法[7]
Cholesky QR は行列積と Cholesky 分解で構成されるQR分解である. 演算密度が高く 1 回の集団通信で計算できるが, 直交性の誤差は行列の条件数の 2 乗に比例して悪化する. PARCEL は 1 回だけ行う方式であり, 繰り返す方式 (CholeskyQR2) は実装していない. Gram 行列はデバイス上で計算し, Cholesky 分解はホスト上で行う.
- アルゴリズム
11.5 モーメント法による Cholesky QR 法 (QR_CAGMRES_CHOLESKYQR)
pcagmresでを作らない場合 (CAGMRES_Q_IMPLICIT. 線形ソルバの章) の最初のブロック () だけで用いる, CA-GMRES 専用の Cholesky QR 法である. 前処理なしの単項式基底 () では, が対称なら (モーメント) となり, Gram 行列は Hankel 行列 () である. は, 4 本と偶数番目の基底の内積個から得られるので, 個の内積を計算しなくてよい. は作らず, だけを返す.
- アルゴリズム
(は 2 以上の偶数) である.
1 行目の行列積はデバイス上で行い, MPI 並列時は局所の値を集約する (集団通信 1 回). Cholesky 分解はホスト上で行う. が対称でない場合や前処理を施した基底ではが Hankel 行列にならず, 誤ったとなる. pcagmresは前処理なしとが偶数であることを入口で検査するが, の対称性は検査しない.