シュトラッセンのアルゴリズムの計算量
シュトラッセンのアルゴリズムという行列積を求めるアルゴリズムがあります。行列積を求めるときに部分行列の積を求めることによって演算回数が少なくて済みます。通常の行列積の演算は \(O(n^3)\) ですが、シュトラッセンのアルゴリズムを使うと \(O(n^{\log_2 7})\) で行えます。巷には日本語だとシュトラッセンのアルゴリズムの説明はちらほらありますが計算量について言及している説明はほとんどないのでしてみようと思います。
サイズNの正方行列の掛け算を考える。因みにシュトラッセンのアルゴリズムを使うときは正方行列でなかったら端に0だけの行or列を追加して無理やり正方行列にする必要がある。Nが2のべき乗でない場合は漸化式が途中で計算できなくなるので途中で諦めるか最初から諦める必要があると思う。以下Nは2のべき乗ということにする。サイズNの正方行列のシュトラッセンのアルゴリズムによる計算時間を \(T(N)\) と書く。シュトラッセンのアルゴリズムでは半分のサイズの行列積を7回求める。行列和の計算量は \(O(N^2)\) なので \[ T(N) = 7 T(N/2) + O(N^2) \] となる。マスターの定理を使うと \(O(N^{\log_2 7})\) となる(らしい)。
マスターの定理はよくわからないのでマスターの定理を使わないで \(T(N) = O(N^{\log_2 7})\) を示す。 \[2^n := N\] として \[U(n) := T(N)\] と書くと \[U(n) = 7 U(n-1) + O(2^{2n})\] となる。漸化式を解く感じで整理すると
\begin{align*} &\frac{U(n)}{2^{2n}} + \frac{4}{3} c \leq \frac{7}{4} \left(\frac{U(n-1)}{2^{2n-2}} + \frac{4}{3}c\right)\ &\leq \left(\frac{7}{4}\right) ^ n \left( U (0) + \frac{4}{3}c\right)\ &\leq \left(\frac{7}{4}\right) ^ n c’ (c’はなんかしらの定数) \end{align*}
となるので \[ \frac{T(N)}{N^2} \leq c’\left(\frac{7}{4}\right) ^ {\log_2 N} \] \begin{align*} T(N) &≤ c’ N^2 \left(\frac{7}{4}\right) ^ {log_2 N} \\ &= c'7 ^ {log_2 N}\\ &= c’N ^ {log_2 7} \end{align*} となり \[ T(N) = O(N^{\log_2 7}) \] が示せた。
計算量解析をしてみたけれど数値計算的にはシュトラッセンのアルゴリズムはほとんど使われない。というのも
- オーダは小さいけど定数が大きいから普通はシュトラッセンのアルゴリズムの方が時間がかかる
- 疎行列だともっといい方法がある
- 部分行列の計算のところでメモリを一杯食う
- 足し引きを一杯行うから浮動小数点演算の誤差が一杯乗る
だからだそうだ。