Flexible GMRES converges in two phases

ステファン・ギュッテルとラウリ・ニマンによる論文「Flexible GMRES Converges in Two Phases」の詳細な技術的要約を以下に示す。

1. 問題の定義

Flexible GMRES (FGMRES) アルゴリズムは、可変前処理を許容する大規模線形連立方程式 $Ax=b$のための標準的な反復ソルバーである。この柔軟性は、前処理行列$M_j$ 自体が反復法である場合（例えば Newton-Krylov 法において）や、行列 $A$ が行列 - ベクトル積を通じてのみアクセス可能である場合に極めて重要である。

広範な利用にもかかわらず、FGMRES の収束理論は未だ十分に理解されていない。特に、内側前処理の残差許容誤差 ($\mu$) が外側 FGMRES ループの収束にどのように影響するかについては不明な点が多い。

• ギャップ: 標準的な GMRES の既存の収束 bound は、残差の多項式表現に依存しているが、前処理が変化するにつれて探索空間が標準的な Krylov 部分空間ではなくなるため、FGMRES においてはこれが成り立たない。
• 問い: FGMRES は前処理の許容誤差 $\mu$ の速度で幾何学的に収束するのか、それとも反復が進むにつれて収束挙動が変化するのか？この手法は停滞し得るのか？

2. 手法

著者らは、FGMRES とFlexible Full Orthogonalization Method (FFOM) の関係に基づいた厳密な収束解析を開発した。

• 再帰的 bound の導出:

  • 彼らは、FGMRES 残差 ($r^{FG}_m$) と FFOM 残差 ($r^{FF}_{m-1}$) および前処理残差 ($r^P_m$) の間に再帰的な関係性を確立した。
  • $r^{FG}_m \perp \text{span}(AZ_m)$ という性質を用いて、以下の不等式を導出した：
    $$\|r^{FG}_m\| \leq \|r^{FF}_{m-1}\| \cdot \|r^P_m\|$$
  • 彼らは、連続する FGMRES 残差の比に関する幾何学的恒等式を介して FFOM 残差と FGMRES 残差を関連付け、縮小係数 $\gamma_m$ に対する再帰的 bound を導出した：
    $$\|r^{FG}_m\| \leq \gamma_m \|r^{FG}_{m-1}\|, \quad \text{where } \gamma_m = \frac{\|r^P_m\|}{\sqrt{1 - \gamma_{m-1}^2}}$$

• チェビシェフ多項式による明示的解:

  • 前処理残差 $\|r^P_j\| \leq \mu$ が一様に有界であると仮定し、縮小係数の漸化式を解析した。
  • 漸化式を線形系に変換することで、縮小係数の積が第 2 種チェビシェフ多項式 ($U_m$) と関連していることを特定した。
  • これにより、残差ノルムに対する事前の閉形式の上限 bound を導出することが可能となった。

• 鋭さの構成:

  • この bound が「鋭い（改善不可能である）」ことを証明するために、著者らは具体的な反例を構成した。任意の線形系および任意の $\mu \leq 1/2$ に対して、FGMRES 残差が導出された上限 bound と完全に一致するような前処理の列（および特定の行列 $A$）が存在することを示した。

3. 主要な貢献

A. 二相の収束挙動

この論文の中核的な発見は、FGMRES の収束が前処理許容誤差 $\mu$ に依存して2 つの明確なフェーズによって支配されることである：

1. フェーズ 1（初期の幾何学的収束）:

   • 反復回数 $m$ が小さい間、収束速度はおよそ $\mu$ である。
   • $\|r^{FG}_m\| \approx \mu \|r^{FG}_{m-1}\|$。
   • このフェーズは $\mu$ が小さい場合（例：$\mu \ll 0.5$）に支配的である。

2. フェーズ 2（劣化または停滞）:

   • $m$ が増加するにつれ、収束速度は $\mu$ から新しい漸近速度 $\nu$ に劣化する。
   • 漸近速度は次式で与えられる：
     $$\nu = \sin\left(\frac{1}{2} \arcsin(2\mu)\right)$$
   • ケース $\mu \leq 0.5$: 速度 $\nu$ は $\mu$ よりわずかに大きい（例：$\mu=0.1$ の場合、$\nu \approx 0.1005$）。非常に小さい $\mu$ の場合、速度は実質的に一定のままとなる。しかし、$\mu \to 0.5$ に近づくにつれ、速度は著しく劣化し、$\nu \approx \sqrt{\mu}$ に近づく。
   • ケース $\mu > 0.5$: この手法は初期の減少フェーズ後に停滞するか、破綻する可能性がある。「ストール指数」$m^*$（停滞に至るまでの反復回数）は、$\mu$ が 0.5 を超えると急速に減少する。

B. 鋭い上限 bound

著者らは、ステップ $m$ における残差に対する以下の鋭い上限 bound を導出した（$\mu \leq 1/2$ と仮定）：
$$\|r^{FG}_m\| \leq \|r_0\| \frac{\mu^{m/2}}{\sqrt{U_m\left(\frac{1}{2\mu}\right)}}$$
ここで $U_m$ は第 2 種チェビシェフ多項式である。

• この bound は達成可能である: 著者らは、等号が成立する線形系と前処理の列が存在することを証明した。
• これは、導出された bound が与えられた仮定の下での FGMRES の最悪ケースシナリオを表していることを意味する。

C. 収束保証条件

この論文は、重要な閾値を確立した：FGMRES が停滞することなく正確な解に収束することが保証されるのは、$\mu \leq 1/2$ である場合に限られる。

• $\mu > 1/2$ の場合、理論的な bound は停滞を許容し、著者らは特定のシステムにおいて実際に停滞が発生し得ることを示した。

4. 結果と数値的実証

理論的な発見は、MATLAB における数値実験によって検証された：

1. 鋭さの検証: 内側 GMRES(100) 前処理（$\mu=0.5$）を持つ構築された $2500 \times 2500$ のシステムにおいて、計算された FGMRES 残差が理論的な上限 bound と完全に一致し、bound が tight であることを確認した。
2. 停滞の図示: $\mu = 0.55$ の場合、残差は初期に減少したが、6 反復後に停滞し、予測された「ストール指数」と一致した。
3. 実世界への応用: 3 次元ポアソン問題（有限要素離散化）からの大規模疎行列において、新しい bound は FGMRES-GMRES の実際の収束挙動を密に追跡し、構築されたシステム以外の実システムにおいてもその実用性を示した。

5. 意義と含意

• 理論的ブレイクスルー: これは、可変前処理許容誤差を明示的に考慮した、FGMRES に対する鋭く達成可能な上限 bound を提供する最初の研究である。優れた内側ソルバーを持つにもかかわらず、FGMRES が期待よりも遅く収束する理由の謎を解明した。
• チューニングの実践的指針:
  • 前処理を調整可能である場合（例：目標残差 $\mu$ を設定するなど）、結果は$\mu \leq 0.5$ を維持することが収束保証のために不可欠であることを示唆している。
  • 非常に厳しい許容誤差（$\mu \ll 0.5$）の場合、二相の挙動は無視でき、手法は速度 $\mu$ で幾何学的に収束する。
  • 緩い許容誤差（$\mu \approx 0.5$）の場合、ユーザーは反復回数が増えるにつれて収束速度が低下することに注意すべきである。
• リスタート GMRES との比較: この論文は、リスタート GMRES が理論的に $O(\mu^j)$ の収束速度を持つ一方で、FGMRES は内側ソルバーが縮小された右辺ベクトルを見ることによる deflate 効果により、実際にはしばしばそれよりも優れていると指摘している。しかし、$\mu$ が 0.5 に近い場合、FGMRES の最悪ケース bound はリスタート GMRES の bound よりも厳密に悪く、柔軟性と最悪ケースの安定性の間のトレードオフを浮き彫りにしている。
• 限界: この解析は $\|r^P_j\| \leq \mu$ が一定であると仮定している。著者らは、ランダム化スケッチングを用いた「fastGMRES」などの手法では $\mu$ が変動し得ることを認めており、そのようなケースへの解析の拡張は未解決の課題である。

要約すると、この論文は FGMRES の収束を決定論的に特徴付け、それが二相で動作し、保証された収束のためのハードリミット（$\mu \leq 0.5$）を確立することを証明しており、鋭い数学的 bound と数値的証拠によって裏付けられている。