シュトラッセンのアルゴリズム

シュトラッセンのアルゴリズム：行列計算の高速化

シュトラッセンのアルゴリズムは、2つのN×N行列の積を、従来のO(N³)の計算量よりも高速に計算するアルゴリズムです。1969年にフォルカー・シュトラッセンによって開発され、O(N^log₂7) ≈ O(N^2.807)という計算量を実現しました。これは、大規模な行列計算において計算時間の劇的な削減につながります。

アルゴリズムの概要

このアルゴリズムは、行列を再帰的により小さな部分行列に分割することで高速化を実現します。まず、Nを偶数と仮定し、N×N行列AとBを以下の様に4つのN/2×N/2部分行列に分割します。


(A₁₁ A₁₂)
(A₂₁ A₂₂)



(B₁₁ B₁₂)
(B₂₁ B₂₂)


これらの部分行列を用いて、以下の7つの行列P₁, P₂, ..., P₇を計算します。

P₁ = (A₁₁ + A₂₂)(B₁₁ + B₂₂)
P₂ = (A₂₁ + A₂₂)B₁₁
P₃ = A₁₁(B₁₂ - B₂₂)
P₄ = A₂₂(B₂₁ - B₁₁)
P₅ = (A₁₁ + A₁₂)B₂₂
P₆ = (A₂₁ - A₁₁)(B₁₁ + B₁₂)
P₇ = (A₁₂ - A₂₂)(B₂₁ + B₂₂)

これらのPᵢから、結果の行列Cの各部分行列Cᵢⱼを以下のように計算します。

C₁₁ = P₁ + P₄ - P₅ + P₇
C₁₂ = P₃ + P₅
C₂₁ = P₂ + P₄
C₂₂ = P₁ + P₃ - P₂ + P₆

このように、通常の行列積の計算に必要な8回のN/2×N/2行列の積を、7回に減らすことで高速化を実現しています。この分割と計算を再帰的に繰り返すことで、最終的にO(N^log₂7)の計算量になります。

アルゴリズムの利点と欠点

シュトラッセンのアルゴリズムは、大規模な行列計算において計算時間を大幅に削減できるという大きな利点があります。しかし、以下の欠点も存在します。

小さな行列には非効率: 行列のサイズが小さい場合は、オーバーヘッドが大きくなり、従来のアルゴリズムよりも遅くなる可能性があります。
数値的安定性の問題: 繰り返し計算による丸め誤差の影響を受けやすく、数値的安定性の問題が生じる可能性があります。
実装の複雑さ: アルゴリズムの実装は複雑で、バグが発生しやすい可能性があります。

まとめ

シュトラッセンのアルゴリズムは、大規模な行列計算の高速化に貢献する重要なアルゴリズムです。しかし、その欠点も理解した上で、適切に適用する必要があります。近年では、さらに高速な行列積アルゴリズムも研究されており、計算機科学の分野において重要な研究テーマとなっています。

関連文献

Ushiro, Y. (1998). An extension of Strassen's algorithm on matrix multiplication, Hitachi, Ltd. General Purpose Computer Division.
Huang, J., Smith, T. M., Henry, G. M., & van de Geijn, R. A. (2016, November). Strassen's algorithm reloaded. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (p. 59). IEEE Press.
Gates, A. Q., & Kreinovich, V. (2001). Strassen's Algorithm Made (Somewhat) More Natural: A Pedagogical Remark. Bulletin of the EATCS, 73, 142-145.
Grochow, J. A., & Moore, C. (2017). Designing Strassen's algorithm. arXiv preprint arXiv:1708.09398.
Ikenmeyer, C., & Lysikov, V. (2017). Strassen's 2x2 matrix multiplication algorithm: A conceptual perspective. arXiv preprint arXiv:1708.08083.
荻田武史, 大石進一, 後保範「Strassen のアルゴリズムによる行列乗算の高速精度保証 (微分方程式の数値解法と線形計算)」『数理解析研究所講究録』第1320巻、京都大学数理解析研究所、2003年5月、151-161頁
* 森山敦史, 荻田武史, 後保範, 大石進一「拡張Strassen法による連立一次方程式の精度保証 (数値解析と新しい情報技術)」『数理解析研究所講究録』第1362巻、京都大学数理解析研究所、2004年4月、47-55頁

もう一度検索