A Jacobi-like algorithm for normal matrices by the skew-symmetric part

技術的概要：斜対称部分による正規行列に対するヤコビ型アルゴリズム

問題定義
本論文は、実正規行列 $A$ の固有値、および任意に固有ベクトルを計算する実正規固有値問題（EVP）を取り扱います。ヤコビ法は対称行列に対する古典的な手法ですが、これを正規行列に拡張することは困難です。Goldstine と Horwitz の手法のような既存の一般化は、しばしば複素演算に依存しており、計算コストが高く、実行列が持つ本来的な構造を無視しています。Zhou と Brent、あるいは Bunse-Gerstner らによる他の実数演算アプローチは、任意の $4 \times 4$ 行列に対する実シュール分解のサブルーチンに依存しており、計算集約的となり得ます。著者らは、並列化の容易さによりヤコビ型アルゴリズムが再び注目されているものの、QR アルゴリズムなどの競合手法と比較して、特に複素固有値を持つ行列において、収束が遅い、または演算回数が多くなる傾向があると指摘しています。

手法
提案される手法は、実正規行列の対称部分と斜対称部分の可換性を活用するヤコビ型アルゴリズムです。中核的な革新は、斜対称行列に対する高速な二次収束アルゴリズムである Paardekooper 法を分解の主要な駆動力として利用することにあります。

アルゴリズム（アルゴリズム 5.1）は、3 つの明確なステップで進行します。

1. ステップ I：陰的 Paardekooper 法
   アルゴリズムはまず、斜対称部分 $\Omega = \text{skew}(A)$ に対して陰的に Paardekooper 法を適用します。$\Omega$ を直接変換するのではなく、$\Omega$ から導出された回転を完全な行列 $A$ に適用します。このステップは、$\Omega$ の非対角ブロックが指定された閾値 $\rho$ 以下に減少するまで続行されます。理論的には、この操作により斜対称部分がブロック対角化され、正規行列の場合、固有値の構造が明らかになります。

2. ステップ II：ブロックの同定と特化対角化
   ステップ I の後、行列 $A$ はまだ完全にブロック対角化されていません。アルゴリズムは、閾値 $\sqrt{\rho}\|A\|_F$ に基づいて $A$ 内の連結成分（非ゼロ部分行列）を同定します。これらの成分は、摂動解析に基づいて 3 種類に分類されます。

   • 対称斜ハミルトニアン（SSkH）ブロック： ブロックが重複した非ゼロの虚部を持つ固有値に対応する場合、摂動を受けた SSkH 行列として扱われます。アルゴリズムは最寄りの SSkH 行列を計算し、対称斜ハミルトニアン行列に対する手法から適応された特化されたヤコビ型手法（アルゴリズム 5.3）を用いて対角化します。
   • 対称ブロック： ブロックが実固有値に対応する場合、摂動を受けた対称行列として扱われます。アルゴリズムは、ブロックの対称部分に対して標準的な対称行列用ヤコビ法（アルゴリズム 5.4）を適用します。
   • 一般ブロック： 摂動が特化手法（例えば、近接するが異なる虚部を持つ固有値など）の適用範囲を超えて大きい場合、そのブロックは一般正規行列ソルバーに渡されます。

3. ステップ III：精度の精緻化
   最終ステップでは、正規行列に対する標準的なヤコビ型アルゴリズム（具体的には Zhou と Brent の手法）を行列全体に適用します。ステップ I と II によって非対角要素が既に大幅に削減されているため、この最終ステップは二次局所収束の恩恵を受け、目標精度 $\rho$ を達成するために非常に少ない掃引回数（通常 1 回または 2 回）で済みます。

主要な貢献

• アルゴリズム設計： 本論文は、斜対称行列に対する Paardekooper 法の速度を活用して実正規 EVP の解決を加速するハイブリッドなヤコビ型アルゴリズムを導入します。
• 陰的変換： この手法は、斜対称部分から導出された変換を直接正規行列に適用し、実数演算を維持するとともに複素数演算を回避します。
• 摂動解析： 著者らは（第 6 節で）厳密な摂動解析を提供し、斜対称部分のシュール分解における不正確さが正規行列の構造にどのように影響するかを定量化しています。この解析は、ステップ II における特定の分岐ロジックを正当化し、特化された SSkH または対称ソルバーと一般ソルバーの使い分けを決定します。
• 最寄行列の公式： 本論文は、摂動境界および特化対角化ステップの設計に不可欠な、最寄りの対称斜ハミルトニアン行列および最寄りの直交シンプレクティック行列の明示的な公式を導出しています（第 8 節）。

結果
数値実験（第 7 節）は、アルゴリズム 5.1 を Bunse-Gerstner ら、Goldstine と Horwitz、Zhou と Brent、およびランダム化手法（RandDiag）という他の 4 つのヤコビ型アルゴリズムと比較しています。

• 精度： アルゴリズム 5.1 は、実固有値を持つもの、重複した虚部を持つもの、ランダムな直交行列など、さまざまな分布を持つ正規行列において、一貫して目標精度（$\text{offschur}(A) \leq \rho \|A\|_F$）を達成します。最も精度の高い競合他社と同等のパフォーマンスを発揮します。
• 効率性： 提案手法は、実行時間の面で他のヤコビ型アルゴリズムよりも 5 倍から 10 倍高速であるという顕著な速度優位性を示しています。この gain は、初期ステップにおける Paardekooper 法の急速な収束に起因し、最終的な精緻化ステップの作業負荷を軽減しています。
• 堅牢性： この手法は、他の手法が困難に直面したり、より多くの反復を必要とする可能性のある、固有値が重複した虚部または密接に配置された虚部を持つ場合でも、堅牢性を維持します。

意義
本論文は、提案アルゴリズムが、特に多様体上の統計に現れるランダムな直交行列のように、ほとんどの固有値が複素数である行列に対する実正規固有値問題の解決において、計算的に優れた代替手段を提供すると主張しています。正規行列の構造的特性と Paardekooper 法の効率性を組み合わせることで、このアルゴリズムは精度を犠牲にすることなく、高い並列性と速度を達成します。著者らは、この手法が斜対称部分が分解のための強力な構造的ガイドを提供する文脈において最も効率的であると指摘し、既存のヤコビ型変種に対する実用的な改善として位置づけています。論文は、再現性のためのオープンソース実装の可用性を強調して結論付けています。