Stabilizing randomized GMRES through flexible GMRES

技術的概要：柔軟な GMRES によるランダム化 GMRES の安定化

問題定義
本論文は、ランダム化クリロフ部分空間法を用いて大規模な疎行列線形方程式 $Ax = b$ を解くという課題に取り組む。ランダム化は低ランク行列近似や過剰決定最小二乗問題に対して極めて効果的であることが証明されているが、一般的な非対称線形方程式への適用はより困難である。過剰決定系とは異なり、一般的な線形系には本質的な冗長性が存在しないため、解ベクトルは行列のすべての成分における摂動に対して敏感となる。その結果、「問題をスケッチする」ことよりも「アルゴリズムをスケッチする」ことの方が実現可能である。

既存のランダム化クリロフソルバ、例えばスケッチ GMRES（sGMRES）は、スケッチ作用素 $S$ を用いて問題を低次元空間に射影することで、標準的な GMRES に伴う高価な直交化コストを削減することを目的としている。しかし、sGMRES は安定性の問題に悩まされている。具体的には、非直交なクリロフ基底を生成するために切断されたアーノルディ法を使用する場合、基底が極めて条件悪化を起こし、停滞や数値的不安定性を引き起こす可能性がある。sGMRES のリスタートは一般的な対策であるが、困難な問題に対しては収束に必要となるリスタート長が許容不可能なほど大きくなるため、しばしば収束に失敗する。

手法
著者らは、**柔軟な GMRES（FGMRES）を外部ラッパーとして用いてスケッチ GMRES（sGMRES）**を安定化させるハイブリッド手法を提案する。中核的な手法は以下の構成要素からなる。

1. 理論的基盤（FGMRES 残差の上限）：
   著者らは、FGMRES 残差に対する新たな実用的な上限を導出した。フル直交化法（FFOM）の柔軟版を導入することで、$m$ 回目の反復における FGMRES 残差 $\|r_m\|$ が、直前の反復における FFOM 残差と内部プリコンディショナ残差の積によって抑えられることを確立した。
   $$\|r_m\| \le \|r_{m-1}^{\text{FFOM}}\| \cdot \|r_m^{\text{precond}}\|$$
   この上限は、内部ソルバ（プリコンディショナ）が効果的に残差を削減すれば、FGMRES と FFOM の残差が同程度に保たれる限り、外部の FGMRES 反復も大域的な残差を削減することを意味する。この理論的結果は、内部ソルバが不安定であっても FGMRES を用いて残差ノルムの非増加を保証する根拠となる。

2. アルゴリズム構造（FGMRES-sGMRES）：
   提案されたアルゴリズム、fastGMRESは、以下のように動作する。

   • 外部ループ： FGMRES 反復を実行する。
   • 内部ループ（プリコンディショナ）： 各外部反復 $j$ において、プリコンディショナ $M_j$ は、$k$ 回の sGMRES 反復を通じて $Az = v_j$ の近似解として計算される。
   • sGMRES 実装： 内部の sGMRES ソルバは、切断されたアーノルディ法（直交化を直前の $t$ 個のベクトルに対してのみ行う）を用いてクリロフ基底 $B_k$ を構築する。解 $z_j$ は、$B_k$ の範囲内でスケッチされた残差 $\|S(v_j - Az)\|$ を最小化することによって見出される。
   • 停止基準： 内部の sGMRES ループは、以下の 3 つの条件に基づいて終了する。
     1. メモリを制御するための最大反復回数制限 $k_{\max}$（例：500）。
     2. 深刻な条件悪化を防ぐためのスケッチ基底 $SAB_k$ の条件数閾値（例：$10^{15}$）。
     3. 推定された FGMRES 残差上限が目標許容誤差を下回ること。

3. パラメータ設定：
   この手法は最小限のパラメータ調整を必要とする。主要なパラメータはアーノルディ切断パラメータ $t$ である。著者らは、直交化を行わない純粋な冪基底（$t=0$）から $t=5$ までを調査した。

主な貢献

• 安定化メカニズム： 本論文は、sGMRES を FGMRES の外部ループで囲むことで、ランダム化ソルバを効果的に安定化させることを実証している。外部ループは残差ノルムの非増加を保証し、リスタート型 sGMRES に典型的な停滞の問題を克服する。
• 新たな残差上限： 上限 $\|r_m\| \le \|r_{m-1}^{\text{FFOM}}\| \cdot \|r_m^{\text{precond}}\|$ の導出は、手法の堅牢性に対する理論的根拠を提供し、内部ソルバのパフォーマンスに基づいて収束を予測するための実用的なツールを提供する。
• 簡素性と堅牢性： 提案された「fastGMRES」手法は、ユーザー入力が必要最小限である。部分空間サイズや除去するベクトル数の慎重な選択を必要とする他の除去リスタート法（GMRES-SDR や RGS-GMRES-MDR など）とは異なり、fastGMRES は固定されたパラメータ（$t=0$ または小さな $t$、固定されたスケッチ次元）で堅牢に動作する。
• $t=0$ による効率性： 著者らは、切断パラメータを $t=0$（内部ループでの直交化なし）に設定することが、特に行列・ベクトル積が安価な問題において、解に至るまでの時間パフォーマンスを最良にすることが多いという直感に反する発見を報告している。

数値結果
著者らは、SuiteSparse 行列コレクションおよび他のベンチマークからのいくつかの困難な問題に対して手法を評価した。

• vas stokes 1M： リスタート型 sGMRES が停滞する困難な問題。FGMRES によって安定化された版は着実に収束する。この手法はリスタート型 sGMRES を大幅に上回り、より少ないパラメータ選択で GMRES-SDR や RGS-GMRES-MDR と競争力がある。
• NACA12： 本手法は ILU プリコンディショニングの有無にかかわらず堅牢に収束する。特筆すべきは、他の手法が困難に直面するかタイムアウトするプリコンディショニングなしのケースであっても、$t=0$ が依然として最速の設定であることである。
• ML Geer： 大規模問題（$n \approx 150$ 万）。すべてのテストされた $t$ に対して手法は堅牢に収束するが、外部 FGMRES 直交化のコストが増大する後期の反復において、$t=0$ はわずかな遅延を示す。
• ベンチマーク： 10 の問題に対する BiCGSTAB、GMRES、GMRES-DR、GMRES-SDR との比較において、fastGMRES は最も信頼性の高いものの一つである。時間制限内で収束に失敗したのは 1 つの問題のみ（他のすべての手法も失敗した）であり、BiCGSTAB は 2 つで失敗している。慎重に調整されたパラメータを持つ GMRES-SDR が時折高速である一方、fastGMRES はパラメータ調整を必要とせずに同等のパフォーマンスを達成する。

意義と主張
本論文は、FGMRES と sGMRES の組み合わせが、効率性、堅牢性、使いやすさのバランスが取れた「実用的なランダム化ソルバ」を提供すると主張している。その意義は以下の点にある。

1. 信頼性： ランダム化またはリスタート型クリロフ法でしばしば失われる、残差ノルムの非増加を保証する。
2. 低い調整オーバーヘッド： 他の高度なクリロフ法を悩ませる複雑なパラメータ選択（除去数やリスタート長など）の必要性を排除する。
3. 計算効率： $t=0$ の驚くべき有効性は、内部ループでの内積を回避することが、特に直交化のための通信がボトルネックとなる並列計算や混合精度シナリオにおいて極めて有益であることを示唆している。

著者らは、この手法が常に最適調整された既存ソルバを上回るわけではないが、幅広い困難な線形系に対して堅牢な「設定して忘れる」代替手段として極めて競争力が高いと結論づけている。今後の研究として、非常に大きな反復数における外部ループの直交化コストを軽減するためのマルチレベル FGMRES 構造の探求が提案されている。