Multilayer approximate nullspace methods for saddle point systems

技術要約：鞍点系に対する多層近似零空間法

問題設定
本論文は、以下の形式で表される、大規模かつ疎な鞍点ブロック構造を持つ線形システムの数値解法を取り扱う。
$$W \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} A & B \\ -C^T & 0 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} f \\ g \end{bmatrix}$$
ここで、$A \in \mathbb{R}^{n \times n}$、$B, C \in \mathbb{R}^{n \times m}$（$m \leq n$）、および $A + A^T$ は半正定値である。これらのシステムは、散逸的ハミルトン系の時間積分、計算流体力学（Navier-Stokes方程式など）、制約付き最適化など、多様なアプリケーションにおいて発生する。著者らは、問題固有の物理的情報に依存しない、純粋に代数的な「ブラックボックス」反復ソルバーの開発に焦点を当てている。研究では、以下の3つの異なるケースを対象としている。

1. 対称型: $B = C$ かつ $A = A^T \geq 0$。
2. 構造的対称型: $B = C$ であるが $A \neq A^T$（ただし $A + A^T \geq 0$）。
3. 一般型: $B \neq C$ かつ $A \neq A^T$（ただし $A + A^T \geq 0$）。

手法
提案されている解法は、外側のクリロフ部分空間法（具体的には再起動型フレキシブルGMRES）内での前処理関数として機能する、新しいクラスの多層反復スキームである。コアとなる手法は、厳密な操作を疎な近似および反復ソルバーに置き換えることで、古典的な厳密零空間法を修正することである。

1. 近似零空間の構築:
   厳密な零空間基底（通常は密行列となる）を計算する代わりに、著者らは**疎近似右斜交共役（SAROC）**アルゴリズムを採用している。この手順では、ピボット選択を伴う斜交共役を実行し、スパース性を維持するためにドロップ許容誤差を適用することで、疎な近似基底（$B^T$ の零空間に対する $\tilde{Z}$、および $C^T$ の零空間に対する $\tilde{U}$）を計算する。

2. 投影零空間行列:
   本手法は、$\tilde{N} = \tilde{Z}^T A \tilde{U}$（一般の場合）または $\tilde{N} = \tilde{Z}^T A \tilde{Z}$（対称の場合）といった投影行列を構成する。理論的解析（補題3）によれば、近似誤差が十分に小さければ、これらの投影行列の対称部分は正定性を保持し、解の存在が保証される。

3. 因子分解型疎近似逆行列（FSAI）:
   投影されたシステムを密行列を明示的に形成することなく効率的に扱うために、投影された零空間行列の対称部分の因子分解型疎近似逆行列（FSAI）を計算する。このステップは、システムをシフト歪対称または対称正定値ソルバーに適した形式へと変換する前処理関数を暗黙的に生成する。

4. 多層反復構造:
   スキームは内側・外側の反復として動作する。

   • 外側ループ: フレキシブルGMRES（fGMRES）がメインの鞍点システムを扱う。
   • 内側レイヤー: 前処理関数の適用には、以下の反復的な部分問題の解決が含まれる。
     • LSQRによる劣決定系の特解の算出。
     • 共役勾配法（CG）（対称ケース）または、シフト歪対称系用の特定の前処理を用いたfGMRES（構造的対称/一般ケース）による、縮退した零空間システムの解決。
     • 最内層のシフト歪対称系を**最小残差（MRS）**法を用いて解決。
   • オプションのM-直交化: 安定性を高めるため（特に悪条件の問題に対して）、零空間基底を $M$-直交化（$M$ は $A$ に関連する）するための修正グラム・シュミット（MGS）ステップを任意で含んでいる。

主な貢献

• 零空間法の一般化: 本論文は、計算コストのためにしばしば無視されてきた、$B \neq C$ かつ $A$ が非対称である一般ケースへと零空間アプローチを拡張している。
• 疎近似戦略: SAROCおよびFSAIを導入することで、厳密な零空間基底に伴う密行列化の問題を回避し、大規模な疎問題に対するスケーラビリティを実現している。
• 理論的解析: 提案された近似投影行列が、たとえ $A$ が不定であっても、あるいは零空間基底が近似的であっても、正定性を保持する条件を確立する厳密な理論的枠組み（定理1、系1、補題3）を提供している。
• 堅牢なソルバークラス: 一貫した代数的枠組みを用いて、対称、構造的対称、および一般の鞍点構造に適応する統一されたソルバークラスを開発した。

実験結果
著者らは、ベースラインとしてILUTP（ピボット付き不完全LU分解）を用いた再起動型GMRES、および対称ケースについては不完全 $LDL^T$ 分解を用いて、提案スキームを評価した。テストは、SuiteSparseコレクションおよびIFISS（流体力学）から生成された行列、およびランダム生成器を用いて行われた。

• 堅牢性: 新しいスキームは優れた堅牢性を示した。対称および一般ケースにおいて、ベースラインのILUTPはゼロピボットや発散により頻繁に失敗したが、新スキームは（一般ケースで非常に緩い許容誤差の場合を除き）すべてのテスト問題で収束した。
• メモリ効率: 非ゼロ要素数（メモリ使用量のプロキシ）の観点では、特に対称および一般ケースにおいて、新スキームは一般にILUTPベースラインよりも少ない非ゼロ要素数を必要とした。
• 反復回数: 新しいスキームは一貫して最大反復制限（1,000回）以内に収束したが、ベースラインは残差許容誤差を満たさないままこの制限に達することが多かった。
• 直交化の影響: 構造的対称および一般ケースでは、M-直交化は収束率に大きな変化を与えなかった。しかし、対称ケースにおいては、高度に悪条件な問題（例：ゴダード・ロケット問題）に対して有益であり、外側の反復回数を大幅に減少させた。

意義と主張
本論文は、提案された多層反復スキームが、問題固有の情報が得られない場合の鞍点系に対する、堅牢かつ効果的な代替手段を提供すると主張している。著者らは、本手法が厳密な零空間法の計算およびメモリ上の欠点を、疎な近似を利用することで克服することに成功したと強調している。

その意義は、広範な鞍点問題（対称から一般まで）を、単一の純粋に代数的な枠組みで扱える点にある。著者らは、現在の実装は「ブラックボックス」的なアプローチであるが、内部の最小二乗ソルバーへの追加の前処理を組み込むことで、さらなる性能向上が可能であると控えめに述べている。また、大規模問題に対する並列実装を今後の課題として挙げている。本手法は、特に、わずかに変化する一連のシステムを解く必要がある、時間変化する、あるいは非線形な散逸的ハミルトン系の暗黙的離散化において特に重要であるとされる。