The shift-and-invert Arnoldi method for singular matrix pencils

技術的概要：特異行列ペンシルに対するシフト・アンド・インバート・アーノルディ法

問題の定義
本論文は、行列ペンシル $A - \lambda B$ が特異（すなわち $\det(A - \lambda B) \equiv 0$）である形式 $Ax = \lambda Bx$ の大規模疎行列一般固有値問題の求解における課題に取り組む。このような場合、任意のスカラーが行列式条件を満たすため、古典的な固有値の定義は機能しない。意味のある解は、「正則」固有値であり、これは $A - \lambda_0 B$ のランクがペンシルの通常ランクより低下する点で定義される。

階段法や QZ 分解のような手法は小規模な密行列問題に対して存在するが、大規模疎行列システムに対しては計算コストが過大となる。Hochstenbach、Mehl、Plestenjak による最近のアプローチは、真の固有値と偽の固有値を分離するために、ランダムに選択された密行列を用いて特異ペンシルを正則化することを提案している。しかし、著者らは、密な正則化行列を使用すると元の問題の疎構造が破壊され、大規模応用において顕著な性能およびメモリオーバーヘッドを引き起こすと主張する。さらに、既存の疎直接ソルバーは、これらのペンシルを正則化するために必要な行/列の削除または追加を、カスタム開発なしにネイティブにサポートしていない。

手法
著者らは、疎 LU 分解のピボット列順を利用することで、特異ペンシルを正則化するための決定論的戦略を提案する。中核となる手法は以下の手順を含む：

1. LU ピボットによる正則化： ランダムな密行列の代わりに、本手法はシフトされた行列 $A - \sigma B$（ここで $\sigma$ はシフト）の疎 LU 分解を使用する。分解の過程で、ゼロ（またはゼロに近い）ピボットに遭遇した場合、アルゴリズムは行列に行と列を追加して分解を維持する。

   • 拡張ペンシル（AGEP）： このプロセスは、拡張ペンシル $\begin{bmatrix} A & G \\ F^* & 0 \end{bmatrix} - \lambda \begin{bmatrix} B & 0 \\ 0 & 0 \end{bmatrix}$ が正則となるような行列 $F$ と $G$ を構築する。行列 $F$ と $G$ は、LU 分解の置換行列とピボット選択プロセスから直接導出される。
   • 射影ペンシル（PGEP）： あるいは、本手法はゼロピボットに対応する行と列を削除することにより、射影ペンシル $G_\perp^* (A - \lambda B) F_\perp$ を構築する。$F_\perp$ と $G_\perp$ は、特定の行が削除された単位行列として導出される。

2. ランク検出と修正： LU 分解は、自然にペンシルの通常ランクを明らかにしようとする。著者らは、丸め誤差や不適切な許容誤差設定により、検出されたランク（$\hat{k}$）が真の通常ランク（$k$）と異なる可能性があることに言及する。

   • 検出されたランクが低すぎる場合（すなわち、許容誤差が過度に厳しすぎる場合）、ランク修正スキームが提案される。これには、検出された $F$ と $G$ を正しい次元に拡張するためにランダムな直交行列を使用し、その後、結果生じる系を解くために低コストのシュール補更新を行うことが含まれる。

3. シフト・アンド・インバート・アーノルディ： 正則化された問題（AGEP または PGEP のいずれか）は、両側シフト・アンド・インバート・アーノルディ法を用いて求解される。著者らは、特定の開始ベクトルと内積を用いた拡張ペンシル上のアーノルディ分解が、射影ペンシルと同じリッツ値とヘッセンベルク行列を生成することを示す等価性定理を証明する。これにより、大規模な拡張系の明示的な構築を回避しつつ、同じスペクトル特性を維持するために射影形式を使用することが可能となる。

4. 長方形問題： この手法は、長方形固有値問題（$A, B \in \mathbb{R}^{n \times m}$、$n \neq m$）に拡張される。フルランクの長方形問題の場合、既存の行ピボット付き疎ソルバーを直接使用して、正方形の正則部分問題を選択することができる。

主要な貢献

• 疎正則化： 本論文は、疎 LU 分解のピボット列順から直接正則化行列（$F, G, F_\perp, G_\perp$）を生成する手法を導入し、元の問題の疎性を保持する。
• ランク検出： 標準的な疎 LU 分解（部分ピボット、ルークピボット、または完全ピボットを使用）は、しばしばペンシルの通常ランクを正常に検出することを示しており、正則化の自動構築を容易にする。
• ランク修正： LU 分解が通常ランクを過小評価した場合に正則化を修正するための特定のアルゴリズムが提案されており、不完全なランク検出があっても手法が堅牢であることを保証する。
• 理論的等価性： 本論文は、アーノルディ法の文脈において、拡張および射影された正則化ペンシル間の厳密な理論的リンクを確立し、特定の条件下で同一のスペクトル近似を与えることを証明する。

結果
数値実験は 3 種類の問題に対して行われた：

1. 有限要素モデル更新： 33 自由度のトラス構造モデル（次元約 35,937 のペンシルを生成）。提案された手法（RLU ピボットを使用）は、ランクを正しく識別し、$10^{-14}$ 程度の残留誤差で固有値を計算した。対照的に、ランダム化アプローチは、条件数が桁違いに高く（$10^6$ 対 $10^3$）、残留誤差も大きかった。
2. 重固有値検出： 2 次元ラプラシアンを離散化したパラメトリック問題。LU ベースの手法は、ランクを正しく決定し、高い精度を達成した。ランダム化アプローチは密行列の構築を必要とし、結果として記憶容量と計算コストが著しく高かった。
3. 長方形非線形固有値問題： 非線形固有値問題から導出されたフルランクの長方形問題。疎 LU アプローチは、分解と射影において著しく高速（0.05 秒対 2.9 秒）であり、ランダム化密アプローチと比較してより少ないメモリ（98MB 対 204MB）を必要とした。

すべてのケースにおいて、疎正則化手法は行列の疎性を保持し、シフトされた系の条件数を低下させ、ランダム化密正則化と比較してより高速な収束をもたらした。

意義と主張
著者らは、この作業を完全な最適化されたソフトウェアソリューションというよりも概念として位置づけ、特異行列に対する堅牢な疎直接ソルバーが標準的なソフトウェアライブラリから現在欠落していることを認めている。しかし、本論文は以下を主張する：

• 性能： 決定論的ピボットを通じて疎性を保持することは、固有値ソルバーの性能と（より良い条件付けを通じて）結果の精度の両方に有益である。
• 実現可能性： 既存の疎直接ソルバーは、特にフルランクの長方形ケースにおいて、新しい複雑なソフトウェアインフラを必要とせずに、これらの問題を求解するように適応可能である。
• 堅牢性： 提案されたランク修正スキームは、LU 分解が通常ランクを完全に検出できなくても手法が機能することを保証する。

本論文は結論として、ランダム化アプローチは理論的に妥当であるが、特異値間のギャップがランク検出に十分であれば、決定論的疎 LU アプローチは、大規模特異固有値問題に対する実用的で効率的かつ正確な代替手段を提供すると述べている。今後の研究として、グローバル最大体積ピボットを備えたソルバーの探求や、多パラメータ問題におけるクリネッカー構造の活用が提案されている。