Convergence analysis of a nonlinear eigensolver based on rational approximation of the resolvent

技術要約：レゾルベントの有理近似に基づく非線形固有値ソルバーの収束解析

問題設定
本論文は、正則な行列値関数 $T$ に対して、$T(\lambda)v = 0$ という形式の非線形固有値問題（NEP）を解く際の課題に取り組んでいる。著者らは、レゾルベント $T^{-1}$ の有理近似の極（pole）を特定することで固有値を計算する、特定のクラスの固有値ソルバーに焦点を当てている。このアプローチは、有理近似のために適応型アンツーラス＝アンダーソン（AAA）アルゴリズムを利用しており、柔軟なフレームワークを提供する一方で、主に以下の2つの制限事項を抱えている：

1. 精度の低下： サンプリング点において高精度な有理近似が得られたとしても、計算された極（固有値）は、特に内部固有値や高次重解の場合、高い精度を欠くことが多い。
2. 重複度の検出： 標準的なスカラー・プロービング・ベクトルを用いる手法では、固有値の重複度を検出できない。なぜなら、得られるスカラー・レゾルベントは、基礎となる代数的重複度に関わらず、単なる極しか持たないためである。

手法
提案手法では、ランダムなプロービング行列 $\Omega_L$ および $\Omega_R$ を用いて、レゾルベントをスケッチすることにより、「サロゲート関数（代理関数）」$F(z)$ を構築する：
$$F(z) := \Omega_L^H T(z)^{-1} \Omega_R$$
アルゴリズムは主に3つの段階で進行する：

1. ブロック・プロービング： スカラー・ベクトルを用いる代わりに、本手法では $n \times b$ のプロービング行列を用いる。この修正は、固有値の重複に関するスペクトル情報を保持し、数値的な堅牢性を向上させるために設計されている。
2. 有理近似： $F(z)$ に対して（集合値）AAAアルゴリズムを適用し、重心形式の有理近似 $R(z)$ を生成する。
3. ズーミング・イン（拡大）： 多くの固有値を含む領域を扱うために、計算領域 $D$ をより小さな部分領域へと再帰的に細分化する。近似あたりの極の数を減らすことで精度を高めるために、これらの小さな領域に対して極探索の手続きを適用する。

最終ステップでは、その重心形式から導出される一般化固有値問題を解くことにより、有理近似 $R(z)$ の極を求める。

主要な貢献と理論的結果
本論文は、この手法の安定性と精度に関する3つの根本的な問いに対して、厳密な収束解析を提供している：

1. ブロック・プロービングによるスペクトルの回復（セクション2）：

   • 著者らは、ブロックサイズ $b$ が固有値の幾何学的重複度以上であれば、サロゲート関数 $F(z)$ はすべての本質的なスペクトル情報を保持することを確立している。
   • 定理 2.3 は、固有値 $\lambda_i$ 近傍における $F(z)$ の特異値が、部分的な代数的重複度によって決定されるレートで増大することを示し、重複度情報の回復が可能であることを示している。
   • 定理 2.7 は、ブロック・プロービングが、スケッチングプロセスによって固有値が見逃される確率（すなわち、スケッチされた係数行列がゼロになる確率）を大幅に減少させることを証明しており、これはベクトルベースのプロービングよりも強力な反集中境界（anti-concentration bound）を提供している。

2. 極の収束とズーミング・インの効果（セクション3）：

   • 定理 3.2 は、極の収束を定量化し、ドメインが大きい場合、重複度 $m$ を持つ計算された極の精度は $O(u^{1/m})$ （ここで $u$ はマシン精度）に制限されることを示している。これは、素朴なアプローチにおいて高次重解の精度が低くなる理由を説明している。
   • 本論文は「ズーミング・イン」技術を分析し、ドメインの直径 $\delta$ を縮小することが、計算される固有値の精度を線形に改善し、$O(u^{1/m})$ の制限を効果的に緩和することを実証している。
   • 定理 3.4 は、複数の極を含むドメインに対する収束結果を提供し、ドメインの分割（近似あたりの極の数を減らすこと）が、特にブロック・プロービングと組み合わせた場合に、精度の大幅な向上につながることを理論的に正当化している。

3. 極探索の安定性（セクション4）：

   • 著者らは、重心形式から派生した一般化固有値問題を通じて、有理近似の根を見つける際の後退安定性と前進安定性を分析している。
   • 定理 4.3 は、計算された極が同時に複数のサポート点に近すぎないという条件下での後退安定性を確立している。
   • 定理 4.4 は、前進安定性を特徴付けており、重複度 $m$ の固有値に対する達成可能な最良の前進誤差は $O(u^{1/m})$ であり、これは古典的な密な固有値ソルバーと一致することを確認している。

結果
数値実験により、理論的知見が検証されている：

• トイ・エグザンプル： 異なる固有値を持つ対角行列に対して、素朴なアプローチ（スカラー・プロービング、単一ドメイン）では、誤差は $10^{-14}$ から $10^{-13}$ 程度となり、最下位桁の数字数が不正確であった。
• 改良されたアプローチ： ブロック・プロービング（サイズ2）とズーミング・イン（ドメインの細分化）を適用することで、少なくとも15桁の精度で固有値を回復した。
• バタフライ問題： 特定のドメイン内に61個の固有値を持つ複雑なNEPにおいて、ブロック・プロービングとドメイン細分化の組み合わせは、単一の大きなドメインを使用した場合と比較して最大誤差を大幅に減少させ、極のクラスターを分離することが精度向上に寄与することを裏付けた。

意義
本論文は、レゾルベントに基づく固有値ソルバーにおいて、ブロック・プロービングとズーミング・インが提供する精度の向上を説明する最初の理論的解析であると主張している。これは以下のことを明らかにしている：

• ブロック・プロービングは、単に重複度を検出するためだけでなく、スケッチングによって失われる可能性のあるスペクトルモードを堅牢に回復するためにも必要である。
• 「ズーミング・イン」技術は、近似ドメイン内の極の密度を減らすことで精度を線形に改善する手法として、理論的に正当化されており、定理 3.2 で特定された収束の限界に直接対処している。
• 手法は、サンプリング点が適切に分布しており、かつ一般化固有値問題が安定して解かれるという条件下で、後退および前進安定である。

著者らは、理論的解析は完了しているものの、偽の極（フロリアセ・ダブレット / Froissart doublets）を除去するための堅牢なクリーンアップ手順の実装は、今後の課題として残されていると述べている。