Strassenのアルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』

Strassenのアルゴリズムは、行列の積を高速に計算するアルゴリズムである。通常、n×n行列同士の積を計算するにはO(n³)時間必要だが、このアルゴリズムを用いると、時間で計算できる。1969年、Volker Strassenが開発した。

便宜上、nを偶数と考えて、以下のようにn/2×n/2部分行列に分解する。

そして、以下の七つの行列をつくる。
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₂₂)

このとき、
C₁₁ = P₁ + P₄ − P₅ + P₇
C₁₂ = P₃ + P₅
C₂₁ = P₂ + P₄
C₂₂ = P₁ + P₃ − P₂ + P₆
の関係が成り立つ。

この関係を利用して計算すると、部分行列同士の乗算が、通常の方法では8回必要なのに、この方法では7回ですむようになり、計算時間が削減される。部分行列への分割を再帰的に行うことにより、さらに計算時間を削減することができる。