3 ms·

Ooh, Matrix multiplication? Would I get to use Strassen's sub-cubic algorithm? I've been looking for an excuse to use it.

signa11 13y ago
afaik, octave uses blas, which in turn should be using strassen's for it's sgemm, dgemm etc. computations. at least it would be very surprising if it didn't...
- James_Duval 13y ago
  Having done a very small amount of research into it I actually think it would be surprising if it did use Strassen's. EDIT: At least frequently, I assume it would use Strassen's for larger matrices much in the same way as introsort works. Apparently it's becoming irrelevant/unwieldy as computing power increases. "Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for small enough submatrices, for which those algorithms are more efficient. The particular crossover point for which Strassen's algorithm is more efficient depends on the specific implementation and hardware. Earlier authors had estimated that Strassen's algorithm is faster for matrices with widths from 32 to 128 for optimized implementations.[1] However, it has been observed that this crossover point has been increasing in recent years, and a 2010 study found that even a single step of Strassen's algorithm is often not beneficial on current architectures, compared to a highly optimized traditional multiplication, until matrix sizes exceed 1000 or more, and even for matrix sizes of several thousand the benefit is typically marginal at best (around 10% or less)." - http://en.wikipedia.org/wiki/Strassen_algorithm http://en.wikipedia.org/wiki/Strassen_algorithm Coppersmith-Winograd, assuming it is not another Galactic algorithm, looks better - http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_al... However I do strongly suspect that this is a Galactic algorithm. In fact, judging from this (http://www-cs.stanford.edu/~virgi/matrixmult-f.pdf http://www-cs.stanford.edu/~virgi/matrixmult-f.pdf), the Big O of time taken for matrix multiplication has been decreasing steadily and without much fuss ever since Strassen. Again, I suspect these are even more galactic algorithms than strassen's is.
  - RogerL 13y ago
    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.

signa11 13y ago

afaik, octave uses blas, which in turn should be using strassen's for it's sgemm, dgemm etc. computations. at least it would be very surprising if it didn't...

James_Duval 13y ago
Having done a very small amount of research into it I actually think it would be surprising if it did use Strassen's. EDIT: At least frequently, I assume it would use Strassen's for larger matrices much in the same way as introsort works. Apparently it's becoming irrelevant/unwieldy as computing power increases. "Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for small enough submatrices, for which those algorithms are more efficient. The particular crossover point for which Strassen's algorithm is more efficient depends on the specific implementation and hardware. Earlier authors had estimated that Strassen's algorithm is faster for matrices with widths from 32 to 128 for optimized implementations.[1] However, it has been observed that this crossover point has been increasing in recent years, and a 2010 study found that even a single step of Strassen's algorithm is often not beneficial on current architectures, compared to a highly optimized traditional multiplication, until matrix sizes exceed 1000 or more, and even for matrix sizes of several thousand the benefit is typically marginal at best (around 10% or less)." - http://en.wikipedia.org/wiki/Strassen_algorithm http://en.wikipedia.org/wiki/Strassen_algorithm Coppersmith-Winograd, assuming it is not another Galactic algorithm, looks better - http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_al... However I do strongly suspect that this is a Galactic algorithm. In fact, judging from this (http://www-cs.stanford.edu/~virgi/matrixmult-f.pdf http://www-cs.stanford.edu/~virgi/matrixmult-f.pdf), the Big O of time taken for matrix multiplication has been decreasing steadily and without much fuss ever since Strassen. Again, I suspect these are even more galactic algorithms than strassen's is.
- RogerL 13y ago
  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.