# 混合精度反復求解法 ## 定義 混合精度反復求解法(mixed-precision iterative refinement、MPIR)は、密線形方程式系 $Ax = b$ を高精度で解くために、低精度の LU 分解と高精度の残差計算・解更新を組み合わせる反復アルゴリズムである。Wilkinson(1940年代)を起源とし、FP32/FP16 アクセラレーションのある現代 GPU 上での高速化手段として再評価されている。 基本的なアルゴリズム(Algorithm 2、Haidar+ SC 2018): 1. 低精度(FP16/FP32)で $A$ の LU 分解を計算 2. FP64 で残差 $r^{(i)} = b - Ax^{(i)}$ を計算 3. 補正方程式 $Ac = r^{(i)}$ を低精度 LU 因子で解く 4. $x^{(i+1)} = x^{(i)} + c$ で解を更新 5. 収束するまで 2〜4 を繰り返す **収束条件(Carson–Higham 2017, 2018)**: - IR(三角求解): $\kappa_\infty(A) < 10^4$(FP16 LU の場合) - IRGM(GMRES 前処理): $\kappa_\infty(A) < 10^8$(FP16 LU の場合) ここで $\kappa_\infty(A) = \|A\|_\infty \|A^{-1}\|_\infty$ は行列の条件数。 **計算量の分解**(Haidar+ SC 2018 の式 (1)(2)): - 主コスト: LU 分解は $O(n^3)$、反復ループ内の残差計算・補正求解は $O(n^2)$ - k 回の反復が必要な場合の合計時間: $\frac{2n^3}{3P_\mathrm{Xgetrf}} + k\left(\frac{2n^2}{P_\mathrm{dgemv}} + \frac{2n^2}{P_\mathrm{Xtrsv}}\right) + \xi$ - FP16-TC は FP64 より $O(n^3)$ 部分が 12× 速いため、少ない反復回数で全体の高速化を実現 ## 横断的知見 - **FP16-TC の FP32 蓄積が分岐点**: テンソルコア(FP16-TC)は乗算を FP16、蓄積を FP32 で行う。この混合精度 GEMM により、単純 FP16 GEMM が発散する行列(クラスタ特異値・複素固有値型)でも収束を維持する。FP16 IR と FP16-TC IR の差は本質的に GEMM 蓄積精度の差である。(Source: [[@2018__SC__Harnessing GPU Tensor Cores for Fast FP16 Arithmetic to Speed up Mixed-Precision Iterative Refinement Solvers]]) - **行列の特性が性能を決める**: FP64 精度ソルバーへの高速化比は固定ではなく、行列の条件数・固有値分布・特異値分布に強く依存する。対角優勢や正固有値の行列では `dhgesv-TC` が安定 4× を示すが、複素固有値・非算術的特異値分布では FP16 IR が発散する。FP32 ソルバー(`dsgesv`)は行列型によらず約 1.7× を安定して達成する。(Source: [[@2018__SC__Harnessing GPU Tensor Cores for Fast FP16 Arithmetic to Speed up Mixed-Precision Iterative Refinement Solvers]]) - **深層学習とは目的が異なる**: 深層学習の混合精度訓練([[混合精度訓練]])は FP16/BF16/FP8 で近似解を「十分な精度」で得ることを目的とし、収束精度の保証は要求しない。一方、HPC の混合精度反復求解法は低精度 LU を**高速な前処理/因子分解器**として用い、最終的に FP64 水準の前進誤差・後退誤差を保証することを目的とする。両者は低精度演算器の活用という手段を共有するが、精度保証の哲学が根本的に異なる。(Source: [[@2018__SC__Harnessing GPU Tensor Cores for Fast FP16 Arithmetic to Speed up Mixed-Precision Iterative Refinement Solvers]] / [[@2023__arXiv__FP8-LM Training FP8 Large Language Models]]) ## 未解決の問い - GMRES(IRGM)の反復回数は行列の型・条件数・サイズに依存し予測困難。非正規行列での収束率を事前に見積もる手法はあるか - FP8 演算をサポートするハードウェア(NVIDIA H100、Hopper)では FP8 LU 分解を利用した IR が実現可能か。条件数制約はどう変わるか - 三精度スキーム(FP16 LU + FP32 作業精度 + FP64 残差)は実用的なソルバーとして MAGMA に実装されているか。二精度スキームとの性能差は - 分散・マルチ GPU 環境での IRGM は通信オーバーヘッドをどう扱うか。先読み(lookahead)技術による隠蔽は GMRES 反復内でも有効か - 疎行列への拡張はどの程度難しいか。密行列向けの知見は疎 LU(PARDISO・SuperLU 等)に転用できるか ## 関連 - 隣接 concept: [[混合精度訓練]] / [[テンソルコア]] / [[GPU最適化]] - 実装: [[MAGMA]](UTK ICL) - 関連エンティティ: [[Azzam Haidar]] / [[Jack Dongarra]] / [[Nicholas J. Higham]] - 関連 MOC: [[分散深層学習 - MOC]] ## 出典 - [[@2018__SC__Harnessing GPU Tensor Cores for Fast FP16 Arithmetic to Speed up Mixed-Precision Iterative Refinement Solvers]] — SC 2018。Haidar, Tomov, Dongarra, Higham。FP16-TC 混合精度 IR フレームワーク。V100 上で FP64 比最大 4× 高速化