Re:Machine Learning Course Materials
by RogerL on Tuesday August 06, 2013 @12:54PM
(#6167664)
Right. Basically, Strassen's is not friendly to the cache - any improvement you get in the asymptotic behavior is usually swamped by the cost of cache misses.
In that vein, the naive implementation (O(n^3)) implementation is also not cache friendly - if you flip the inner loops you will get far better performance (in row major languages).
But I mainly replied because I love the concept of "galactic algorithms" and Regan&Lipton (orignators of the idea and name).
EDIT: the BLAS routine in question is dgemm.f (double general matrix multiply) and is easily googled so I won't paste it here. No Strassen's in sight.
In that vein, the naive implementation (O(n^3)) implementation is also not cache friendly - if you flip the inner loops you will get far better performance (in row major languages).
But I mainly replied because I love the concept of "galactic algorithms" and Regan&Lipton (orignators of the idea and name).
EDIT: the BLAS routine in question is dgemm.f (double general matrix multiply) and is easily googled so I won't paste it here. No Strassen's in sight.