Strassenアルゴリズムのまとめ

Strassenアルゴリズムとは

行列の乗算に対して、時間計算量 \mathcal{O}(n^{3})の愚直な方法より効率よく、 \mathcal{O}(n^{2.81\dots})で求めることができる方法である。

アルゴリズム

乗算を実施したい行列 Aと Bを半分に分割する。

\begin{equation} \left( \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right) \times \left( \begin{array}{cc} b_{11} & b_{12} \\ b_{21} & b_{22} \end{array} \right) = \left( \begin{array}{cc} c_{11} & c_{12} \\ c_{21} & c_{22} \end{array} \right) \end{equation}

すると、

\begin{eqnarray} c_{11} &=& a_{11}b_{11} + a_{12}b_{21} \\ c_{12} &=& a_{11}b_{12} + a_{12}b_{22} \\ c_{21} &=& a_{21}b_{11} + a_{22}b_{21} \\ c_{22} &=& a_{21}b_{12} + a_{22}b_{22} \\ \end{eqnarray}

となるが、ここで以下のような p_{i} (i=1, 2, \dots, 7)を導入する。

\begin{eqnarray} p_{1} &\equiv& a_{11}(b_{12}-b_{22}) \\ p_{2} &\equiv& (a_{11}+a_{12})b_{22} \\ p_{3} &\equiv& (a_{21}+a_{22})b_{11} \\ p_{4} &\equiv& a_{22}(b_{21}-b_{11}) \\ p_{5} &\equiv& (a_{11}+a_{22})(b_{11}+b_{22}) \\ p_{6} &\equiv& (a_{12}-a_{22})(b_{21}+b_{22}) \\ p_{7} &\equiv& (a_{11}-a_{21})(b_{11}+b_{22}) \\ \end{eqnarray}

すると、

\begin{eqnarray} c_{11} &=& -p_{2}+p_{4}+p_{5}+p_{6} \\ c_{12} &=& p_{1}+p_{2} \\ c_{21} &=& p_{3}+p_{4} \\ c_{22} &=& p_{1}-p_{3}+p_{5}-p_{7} \\ \end{eqnarray}

と表すことができる。 p_{i}で出現する乗算はAとBの半分のサイズの行列演算なので、これを再帰的に実施することで乗算を求めるアルゴリズムである。

時間計算量

n\times n行列の乗算にかかる時間計算量を f(n)とすると、

\begin{eqnarray} f(n) &=& 7f(\frac{n}{2}) \\ &=& 7^{2} f(\frac{n}{2^2}) \\ &=& \dots \\ &=& 7^{\log_{2}n} f(1)\\ &=& 7^{\log_{2}n} \\ &=& n^{\log_{2}7} \\ &=& n^{2.81\dots} \end{eqnarray}

途中で

\begin{equation} a^{\log_{b}c} = c^{\log_{b}a} \end{equation}

が一般に成り立つことを利用した。

ポイント

p_{i}が8種類ではなく7種類で十分であるというところに本質がある。仮に p_{1}=a_{11}b_{11}、 p_{2}=a_{12}b_{21}などとして、要素をそれぞれ pとした場合はpは8種類必要だとわかるが、この場合は時間計算量は \mathcal{O}(n^{\log_{2}8})=\mathcal{O}(n^{3})となり愚直な計算と同じ計算量となることがわかる。8回乗算を実施しないといけないように見えて、実は7回で済むという点がポイントである。

補足

Strassenアルゴリズムよりも計算量を落とせるアルゴリズムがあるらしい。こちらの論文には

Denoting by ω the matrix exponent, the quantity such that O(n ω) is the best asymptotic upper bound on the bilinear rank of the product of n × n matrices in C, a lot of contributions [18, 15, 16, 43, 55, 61] improved the upper bound on ω. The best bound known is due to Williams and Le Gall [61] and is equal to 2.3729, although the bound proposed by Coppersmith and Winograd [18], equal to 2.376, is often used as a reference.

とある。

不明点

  • p_{i}の表現はどのように導出されるのか。

参考

www.slideshare.net