3 ms·

You should benchmark, but you are probably wrong. The whole talk was about how hardware (i.e. memory accesses) matters. Even the Wikipedia article you linked to

by dottrap 13y ago

You should benchmark, but you are probably wrong. The whole talk was about how hardware (i.e. memory accesses) matters. Even the Wikipedia article you linked to suggests this. "Earlier authors had estimated that Strassen's algorithm is faster for matrices with widths from 32 to 128 for optimized implementations. 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)."

betterunix 13y ago
Sure, but that benefit will become increasingly large as the problem size is increased. Benchmarking should be done, of course, but only as a way to determine where Strassen's algorithm begins to dominate. Note also that that quote supports what I said, at least in the limit: Strassen's algorithm does improve performance more dramatically for large problem sizes (though how much more dramatically is certainly debatable). I am not going to deny that hardware matters, but it is important to know where it matters. Hardware matters in terms of constant factors. For sufficiently large problem sizes, hardware might give you a 10x improvement if you use it correctly -- but that is 10x no matter how large the problem size becomes. An algorithmic improvement will become increasingly beneficial as the problem size increases; that is why we speak of things like "crossing points," where an asymptotically faster algorithm begins to dominate. Even very poor use of hardware features (terrible locality of reference, etc.) will eventually be irrelevant for an asymptotically better algorithm; a large number of really good uses of the hardware is still slower than a small number of really bad uses.
- comefrom30 13y ago
  Sometimes the problem size doesn't increase. Sometimes you maybe just need to do lots and lots and lots and lots of small matrix multiplications.

by dottrap 13y ago

betterunix 13y ago

Sure, but that benefit will become increasingly large as the problem size is increased. Benchmarking should be done, of course, but only as a way to determine where Strassen's algorithm begins to dominate. Note also that that quote supports what I said, at least in the limit: Strassen's algorithm does improve performance more dramatically for large problem sizes (though how much more dramatically is certainly debatable). I am not going to deny that hardware matters, but it is important to know where it matters. Hardware matters in terms of constant factors. For sufficiently large problem sizes, hardware might give you a 10x improvement if you use it correctly -- but that is 10x no matter how large the problem size becomes. An algorithmic improvement will become increasingly beneficial as the problem size increases; that is why we speak of things like "crossing points," where an asymptotically faster algorithm begins to dominate. Even very poor use of hardware features (terrible locality of reference, etc.) will eventually be irrelevant for an asymptotically better algorithm; a large number of really good uses of the hardware is still slower than a small number of really bad uses.

comefrom30 13y ago
Sometimes the problem size doesn't increase. Sometimes you maybe just need to do lots and lots and lots and lots of small matrix multiplications.