Reducing Internal State in Eigenvalue-Only Divide-and-Conquer Tridiagonal Eigensolvers

技術概要：固有値のみの分割統治法による対角化ソルバにおける内部状態の削減

1. 問題定義

対称行列の固有値分解（EVD）は、科学技術計算における基本的な操作である。標準的なパイプラインは、密な対称行列を対角化前に三重対角形式 $T$ に変換するが、三重対角段階におけるソルバの選択は、固有ベクトルが必要かどうかによって大きく依存する。

• QR/QL 法: 固有値のみの計算の場合、標準ライブラリ（例：LAPACK の xSTERF）は QR ベースのアルゴリズムをデフォルトとする。これらはメモリ効率が良い（$O(n)$ の空間）が本質的に逐次的であり、現代のマルチコア CPU や GPU における性能を制限する。
• 分割統治法（D&C）: D&C は大規模システムにおいて優れた並列性と速度を提供する。しかし、従来の D&C 実装（例：LAPACK の xSTEDC）は、固有値のみが要求された場合でも二次的なメモリフットプリント（$O(n^2)$）を維持する。これは、部分問題をマージするために必要なランク 1 更新ベクトルを構築するため、アルゴリズムが密な固有ベクトル行列を保存するか「再生」しなければならないからである。
• ギャップ: 既存の「遅延再生（lazy-replay）」定式化は不要な積極的な乗算を削減するが、累積された直交変換の二次的なメモリフットプリントは維持したままとなる。これにより、特にデバイスメモリが制約される GPU 上では、メモリ不足を避けるために、固有値のみのタスクに対してより遅い QR 法をデフォルトとして選択せざるを得ない状況となっている。

2. 手法：境界行 D&C

本論文は、固有値のみの D&C プロセスのデータ依存性を根本的に変更する境界行（BR）D&C アルゴリズムを提案する。

• 核心的な観察: D&C におけるマージステップは、対角行列にランク 1 行列を加えた行列に対するセクシャル方程式を解く。ランク 1 更新ベクトル $v$ は、左の子の固有ベクトル行列の最後の行と、右の子の固有ベクトル行列の最初の行にのみ依存する。完全な固有ベクトル行列は必要ない。
• アルゴリズム的不変量: 完全な固有ベクトル行列を伝播させたり、密な変換履歴を再生したりする代わりに、BR アルゴリズムは祖先のマージに必要な境界行（固有ベクトルブロックの最初と最後の行）のみを伝播させる。
• 状態の伝播:
  • 再帰ツリー内の各ノードにおいて、アルゴリズムは子ノードの境界行と局所的なセクシャル固有ベクトルから、親の固有ベクトルブロックの境界行を直接計算する。
  • これは選択された行の更新によって達成される：$(Q_{parent})_{\sigma} = (Q_{child})_{\sigma} S$。ここで $\sigma$ は必要な特定の境界行を表す。
  • アルゴリズムは、完全な $K \times K$ のセクシャル固有ベクトルブロックや密な変換行列を具体化（materializing）することを回避する。
• 正しさと安定性:
  • 正しさ: 定理 3.3 は、厳密な算術において、BR が従来の D&C と全く同じセクシャル問題を構築し、同一の固有値を返すことを証明する。
  • 安定性: 誤差伝播は、標準的な局所的な安定性インターフェース（セクシャル方程式ソルバとデフレーション処理）に条件付けられる。境界行の伝播は、結合のノルムを超えて誤差を増幅しない。

3. 複雑性解析

• 空間複雑性: 最も顕著な改善は補助記憶領域において見られる。
  • 従来の D&C: 密な固有ベクトル/再生状態のための $O(n^2)$ の実数ワークスペース。
  • BR D&C: $O(n)$ の補助ワークスペース。アルゴリズムは極点配列、コンパクトなセクシャルデータ、および選択された境界行のみを保存する。
• 時間複雑性:
  • 最悪の場合（デフレーションが弱い場合）、セクシャル根求解の漸近的コストは $O(n^2)$ のままとなる。
  • しかし、BR は密な局所セクシャルベクトルブロックと再生メタデータの再構築および具体化に関連する $O(n^2)$ のコストを排除する。
  • 主要なマージパスのコストは定数倍で削減される：$T_{BR}(n) \approx (2c_{sec} + 4)n^2$ に対し、$T_{lazy}(n) \approx (2c_{sec} + 2c_{rep} + 8)n^2$ である。

4. 実装と評価

著者らは、このアルゴリズムを CPU（OpenMP 使用）および GPU（CUDA 使用）プラットフォーム上で実装し、標準的なベースラインと比較した。

• CPU 実装:

  • 三重対角段階を分離するために、プライベートな LAPACK 風のドライバ（DSTEDC_DC_BR）が作成された。
  • 結果: 56 コアの Intel Xeon システムにおいて、BR は標準的な QR/QL ルーチン（DSTERF）よりも大幅に高速であり、ランダム入力に対して $N=65,536$ で4,000 倍から 5,000 倍の高速化を達成した。
  • MKL の内部の固有値のみの D&C パス（二次メモリを使用）と比較して、BR は3.1 倍から 6.1 倍高速でありながら、桁違いに少ないメモリを使用していた（例：$N=16,384$ で 2.44 MiB 対 6.0 GiB）。
  • BR は $N=134,000,000$ で 32 ビットワークスペースの限界に達するまで正常に実行されたのに対し、内部 D&C パスははるかに小さいサイズで失敗（OOM）した。

• GPU 実装:

  • NVIDIA H100 上で常駐 CUDA カーネルとして実装された。
  • 結果: NVIDIA の cuSOLVER cusolverDnXstedc（固有値のみのモード）と比較して、BR プロトタイプは $N=49,152$ で1.74 倍から 5.73 倍高速であった。
  • メモリ: cuSOLVER のワークスペースは二次的に増加し、$N=49,152$ で54.0 GiBに達したが、BR プロトタイプは約1.5 GiBしか使用しなかった。

5. 主要な貢献

1. 依存関係の特定: 固有値のみの D&C は、マージを実行するために完全な固有ベクトル行列ではなく、境界行のみを必要とすることを特定した。
2. 境界行アルゴリズム: これらの境界行のみを伝播させる新しいアルゴリズムにより、補助メモリを $O(n^2)$ から $O(n)$ に削減した。
3. 理論的保証: 正しさ（従来の D&C と同一の固有値）および条件付き誤差安定性の証明。
4. 高性能実装: 二次的なメモリペナルティなしに D&C の並列性を露出させる CPU および GPU プロトタイプ。
5. 実証的検証: BR がメモリ制約のある固有値のみのワークロードに対して D&C を実用的にし、速度とスケーラビリティにおいて QR/QL および既存の内部 D&C ルーチンを凌駕することを示す広範なベンチマーク。

6. 意義と主張

本論文は、固有値のみの D&C 変種を、退化した固有ベクトルアルゴリズムとして扱うべきではないと主張する。より小さなデータ依存性（境界行のみ）を利用することで、主要な理由（フル固有ベクトル状態の保持）を排除しつつ、D&C の並列マージ構造を維持することが可能である。

• 控えめな主張: 著者らは明示的に、BR が万能の二次未満の固有値ソルバではないと述べている。デフレーションが弱い場合（例：トープリッツ行列やクラスタリングされたスペクトル）、セクシャル根求解の作業は $O(n^2)$ のままとなり、QR に対する高速化は定数倍とスレッド化の恩恵に限定される。
• 主要な価値: その意義は、フル固有ベクトル状態を伴わずに固有値のみのワークロードに対して D&C の設計点を利用可能にすることにある。これは、二次的なワークスペースがデバイスメモリに大規模な問題を収容できない原因となる GPU 計算において特に重要である。この研究は、QR のメモリ効率と D&C の並列性能の間のギャップを埋めている。