nlKrylov: A Unified Framework for Nonlinear GCR-type Krylov Subspace Methods

技術要約：NLKRYLOV – 非線形GCR型Krylov部分空間法のための統一フレームワーク

問題提起
本論文は、連続微分可能な関数 $f: \mathbb{R}^n \to \mathbb{R}^n$ に関する非線形方程式系 $f(x) = 0$ の数値解法を取り扱っている。このクラスの問題は、ODE/PDEソルバーや無制約最適化（最適条件 $\nabla \phi(x) = 0$ を通じて）において基礎となるものである。不動点反復やニュートン型の手法は標準的であるが、不動点スキームは収束の遅さや収束の保証の欠如に悩まされることが多く、また、ニュートン法は高価なヤコビアンの計算や近似を必要とする。Anderson Acceleration (AA) や準ニュートン法といった既存の加速技術は、反復の差分をサンプリングするが、非線形問題におけるKrylov部分空間の構造を十分に活用できていない可能性がある。

手法
著者らは、古典的な線形入れ子型Krylovソルバー（特にGCR型の手法）を非線形系へと一般化した統一フレームワークである nlKrylov を提案している。このフレームワークは、部分ルーチン $SR_j$ を中心としたモジュール構造を持つ、非線形切断型一般化共役残差（nlTGCR）法に基づいている。

1. 統一フレームワークの構造:
   コアとなるアルゴリズム（Algorithm 3）は、探索方向の集合 $P_j$ とヤコビアン関連ベクトル $V_j$ を保持する。各反復 $j$ において、更新 $x_{j+1} = x_j + P_j y_j$ は、$P_j$ で張られる部分空間内での残差ノルムの最小化によって計算される。

   • 部分ルーチン $SR_j$: フレームワークの際立った特徴は、線形部分問題 $J_f(x_j) b_p = r_j$ を近似的に解く部分ルーチン $SR_j(r_j, J_f(x_j))$ である。これにより、任意の適切な線形ソルバーを用いて探索方向 $b_p$（およびその後の $P_j$）を構築することが可能になる。
   • 入れ子状のアルゴリズム: $SR_j$ として特定の内部ソルバーを選択することで、本フレームワークは確立された線形手法の非線形拡張を生成する：
     • nlGMRESR: 内部ソルバーとして $m$ ステップのGMRESを使用する。
     • nlGCRO: 外部基底 $V_j$ を射影して情報を再利用する、デフレットGMRESを使用する。
     • nlLGMRES: 外部基底 $P_j$ を内部Krylov部分空間に含める、拡張GMRESを使用する。

2. 既存手法との関連性:
   本論文は、nlKrylov法が以下のように見なせることを示している：

   • 準ニュートン法: これらは $x_{j+1} = x_j - P_j V_j^T f(x_j)$ という形式の更新を行い、逆ヤコビアンのランク $n_j$ 近似 $G_j \approx P_j V_j^T$ を実質的に使用している。
   • 不完全ニュートン法: 本フレームワークは、内部ソルバーが強制項を制御する不完全ニュートン理論の枠組みに適合する。
   • 部分空間投影ニュートン法: これらの手法は、動的に構築される部分空間を用いる、部分空間投影アプローチ（PAA）と関連付けられている。

3. 実装の詳細:

   • 適応的線形化: 計算コストを削減するため、非線形残差と線形化残差の間の角度条件に基づいて、非線形残差更新と線形化更新を切り替えることができる。
   • リスタート: 非線形設定におけるヤコビアンの変化によって引き起こされる基底行列 $P_j$ および $V_j$ の悪条件化を管理するために、自動リスタート戦略が採用されている。
   • 行列値への拡張: 本フレームワークは、グローバルKrylov部分空間技術とフロベニウス内積を利用することで、行列値方程式 $F(X)=0$ を解くように拡張されている。

主な貢献

• 統一フレームワーク: 本論文は、線形入れ子型Kryлоv再利用戦略を非線形領域へと一般化するための一般的な理論的構造を提供し、それらがnlTGCRおよびnlOrthominに対してどのように関係しているかを明確にしている。
• 収束理論:
  • 非特異なヤコビアンを持つ問題に対して、著者らは緩和された仮定の下での局所収束を証明している。具体的には、厳密なラインサーチや誤差行列の一様境界を必要とせず、部分空間近似の質 $\mu_j$ と残差減少 $\eta_j$ を測る条件 $\mu_j + \eta_j \leq c < 1$ に依存している。
  • 特異なヤコビアン（特に1次元の零空間を持つもの）に対しては、強制シーケンスが特定の二次的な境界を満たす場合、零空間方向に速度 $1/2$ で線形収束するという結果が導出されている。
• アルゴリズムのバリエーション: 特定のアルゴリズム（nlGMRESR, nlGCRO, nlLGMRES）の導出と、それらの計算コスト（関数評価回数および内積回数）の比較分析が提示されている。

結果
以下の4つのベンチマーク問題を用いて、広範な数値実験が行われた：

1. Lennard-Jones問題: 分子最適化問題。
2. Chandrasekhar H-方程式: 非特異および特異なヤコビアンの両方のケースを持つ積分方程式。
3. 対称Bratu問題: 非線形PDEの離散化。
4. 非線形代数リッカチ方程式 (NARE): 行列値根探索問題。

知見:

• 性能: nlGMRESR は、様々な問題とパラメータ設定において、最も堅牢な性能を一貫して示した。
• 部分空間のリサイクル: nlGCRO と nlLGMRES は、ヤコビアンが緩やかに変化する問題（例：Bratu問題）において、外部基底を再利用することで収束が改善されるという、標準的なnlGCRに対する顕著な利点を示した。ただし、その性能は問題依存性が高かった。
• ベースラインとの比較:
  • nlKrylov法は、一般にnlGCRやnlOrthominよりも少ない外部イテレーションを必要とした。
  • 総関数評価回数の観点では、nlKrylov法はJacobian-free Newton-Krylov (JFNK) や Anderson Acceleration (AA) と同等の競争力を持っていた。
  • nlOrthomin は、イテレーション数はnlGCRと同程度であったが、厳密なラインサーチの要求により、関数評価コストが大幅に高くなった。
  • AA は、特定のケース（例：特異なH-方程式）において実行時間の面で最速であったが、注意深いチューニングを必要とした。
• 特異な問題: 適応型バリアント（例：nlGCR-A）は、純粋な非線形手法が停滞したケースにおいて、線形更新への切り替えメカニズムの有用性を実証し、停滞を克服することに成功した。

意義
本論文は、nlKrylovフレームワークが、線形Krylov再利用戦略を非線形問題へと一般化するための体系的な方法を提供すると主張している。それは、Krylov部分空間法、準ニュートン更新、および不完全ニュートン・スキームの間の理論的な架け橋を提供する。著者らは、これらの手法がNewton-Krylovの均一な代替物ではなく、補完的なクラスのソルバーであることを強調している。その主な利点は、ヤコビアンが緩やかに変化するシナリオにおいて効果的な部分空間リサイクルが可能であること、および行列値問題に対して柔軟な構造を提供することにある。本研究は、非線形加速の理論的背景を明確にし、局所的な線形モデルの精度と計算オーバーヘッドのバランスを取る実用的なアルゴリズムを提示している。