C
アルゴリズム
初心者
行列

非再帰で再帰的にシュトラッセンのアルゴリズムを適用した場合の速度の比較

More than 1 year has passed since last update.

行列積の高速化を行いたかったので試した
正方行列の同士の積の速さを調べた
再帰関数は遅そうなのでとりあえず非再帰にした

ソースコード

https://github.com/2a3oiUA3zfDtr3py/Misc/tree/master/Strassen_test

環境

ディストリ Gentoo
linux 4.12.0
gcc 6.4.0
コンパイルオプション O3 のみ

結果

サイズが500〜700くらいでシュトラッセンのアルゴリズムが優位になる
適用回数を増やしすぎると遅くなる

0(通常版) 1 2 3 4 5
1024 8.004014 5.214240 4.795226 4.853635 4.749052 6.112296
768 2.436310 2.250368 2.108333 2.306208 2.312872 3.133664
512 0.630759 0.658321 0.667544 0.657491 0.850998 1.256109
386 0.268798 0.284696 0.312598 0.312704 0.433152 0.698134
256 0.075986 0.089913 0.087577 0.114589 0.173926 0.308808

自分が扱いたいサイズが64*64なのでシュトラッセンのアルゴリズムによる高速化は望めない…