8 ms·
Strassen has _not_ stood as the fastest way, whether you look at the exponent or the constant factor. It's probably more accurate to say Strassen was the first
by xdavidliu 4y ago
Strassen has _not_ stood as the fastest way, whether you look at the exponent or the constant factor.
It's probably more accurate to say Strassen was the first in a series of complexity improvements to matrix multiplication, most of whom are theoretical curiosities and have prohibitively high constant factors preventing them from ever been used in practice.
Even if all you cared about was the exponent, Strassen was beaten decades ago.
https://en.wikipedia.org/wiki/Matrix_multiplication#Computational_complexity https://en.wikipedia.org/wiki/Matrix_multiplication#Computat...
- falseprofit 4y agoIn practice, the constant factor and the exponent need to be considered together. The constant factor on its own is very uninteresting, practically meaningless without the exponent. >”Even if all you cared about was the exponent” There are really only two things to care about: the exponent on its own, or practical runtime. The claim is that there is a significant range of computations for which Strassen has stood as the fastest.
- xdavidliu 4y ago> The claim is that there is a significant range of computations for which Strassen has stood as the fastest. Interesting, I wasn't aware of this. Where is this claim made, and for which significant range of computations?
- xdavidliu 4y ago> The claim is that there is a significant range of computations for which Strassen has stood as the fastest. Thought about this some more, and I'm gonna conclude two things: - that claim wasn't made in any articles - if made, that claim would be incorrect.