Computing matrix functions associated with a Hermitian--definite pencil

問題の定式化
本論文は、$\phi(A, B) := Af(A^{-1}B)$ の数値的評価を取り扱います。ここで、$A \in \mathbb{C}^{n \times n}$ はエルミート正定、$B \in \mathbb{C}^{n \times n}$ はエルミート、$f$ は $A^{-1}B$ のスペクトル上で定義された関数です。この問題は、エルミート - 定値行列束 $B - \lambda A$ の文脈で生じ、各種の行列平均（算術平均、調和平均、幾何平均など）の計算および常微分方程式系の解法において中心的な役割を果たします。著者らは、中程度のサイズの行列に対する完全な行列 $\phi(A, B)$ を計算する問題 P1 に焦点を当てています。主要な課題は、数値的に不安定となり得る $A^{-1}B$ の明示的な形成を避けつつ、数値的安定性を維持しながら計算コストを最小化することです。

手法とアルゴリズム
著者らは、この問題の条件付けを分析し、行列束のスペクトル特性を活用するいくつかのアルゴリズムを提案します。彼らは等価式 $\phi(A, B) = A^{1/2}f(A^{-1/2}BA^{-1/2})A^{1/2}$ を利用して、問題をエルミート行列の関数評価に変換します。本研究では、5 つの具体的な実装を比較します。

1. Naive（単純法）: $A^{-1}B$ を明示的に計算し、$f$ を適用します。
2. Sqrt Schur（アルゴリズム 1）: 行列平方根 $A^{1/2}$ を計算し、$A^{-1/2}BA^{-1/2}$ を形成した後、シュール分解を行い、固有値に $f$ を適用して結果を再構成します。
3. Schur Schur（アルゴリズム 2）: 行列平方根を明示的に計算することなく、2 つのシュール分解（$A$ 用と変換された行列用）を使用します。
4. Chol Schur（アルゴリズム 3）: 行列平方根と逆行列の計算を、コレスキー分解 $A = R^*R$ に置き換えます。$R^{-1}BR^{-*}$ を計算し、シュール分解を行い、結果を再構成します。
5. Chol Schur PD（アルゴリズム 4）: $B$ もまた正定である場合のアルゴリズム 3 の拡張であり、$A$ と $B$ 双方に対してコレスキー分解を利用します。

著者らは、浮動小数点演算における平方根ベースのアプローチ（アルゴリズム 1）とコレスキーベースのアプローチ（アルゴリズム 3）に対して、詳細な丸め誤差解析を提供します。彼らは前方誤差の明示的な上限を導き出し、総誤差を初期分解に起因する摂動誤差と、その後のステップで蓄積される丸め誤差に分解します。

主要な貢献と結果

• 条件付けの分析: 著者らは $\phi(A, B)$ のフレシェ微分に対する明示的な式を導き、その条件数に対する上限を確立します。これらの上限は、$A$ と $B$ の条件数、ならびに関数 $f$ とその双対の差商に依存します。
• 計算複雑性: 理論的なフロップ数が提供されます。アルゴリズム 1（Sqrt Schur）は約 $27n^3$ フロップを必要とします。アルゴリズム 3（Chol Schur）はこれを約 $13n^3$ フロップ（さらなる最適化により $(12 + 2/3)n^3$）に削減し、高価な行列平方根を回避することで計算コストを実質的に半減させます。
• 誤差解析: 丸め誤差解析により、アルゴリズム 3 の誤差上限は理論的にアルゴリズム 1 より優れていることが明らかになりました。具体的には、アルゴリズム 1 における摂動誤差は行列平方根に起因して $n^3$ に比例して増大するのに対し、アルゴリズム 3 においてはコレスキー分解に起因して $n$ に比例して増大します。さらに、解析はアルゴリズム 3 の誤差がアルゴリズム 1 に比べて $A$ の条件数に対して感度が低いことを示唆しています。
• 数値実験: 乱数正定行列上で行われた実験は、理論的な予測を確認しました。
  • 精度: コレスキーベースのアルゴリズム（アルゴリズム 3 と 4）は、特に $A$ が悪条件である場合に、著しく高い精度を示しました。これらの前方誤差は、$A$ の条件数に対して、平方根ベースおよび単純な手法に比べてより穏やかに増大します。
  • 性能: アルゴリズム 3 と 4 は最も高速であり、単純な手法を 1〜2 桁、平方根ベースのアプローチを明らかな差で凌駕しました。
  • 比較: 「Chol Schur」と「Chol Schur PD」のバリエーションは、ほぼ同一の性能と精度を示しました。これは、アルゴリズム 4 における $B$ の追加のコレスキー分解が理論的にはわずかな改善をもたらすものの、実用上はアルゴリズム 3 と同等であることを示唆しています。

意義と主張
本論文は、$\phi(A, B)$ の計算において、コレスキー分解に基づくアルゴリズムは、行列平方根に基づくアルゴリズムよりも精度が高く、効率的であると主張します。著者らは、数値実験が理論的解析を確認しており、コレスキーベースの手法が計算コストと数値的安定性のより良いバランスを達成していることを示していると述べています。彼らは結論として、中程度のサイズの行列に対しては、コレスキー - シュールアプローチ（アルゴリズム 3）が望ましい手法であると結論付けています。本論文は明示的に、生成される稠密行列を格納できない大規模な疎行列の場合（問題 P2）には言及しておらず、そのようなケースはクリロフ部分空間法のような異なる手法を必要とし、今後の課題として残されると指摘しています。