3 ms·
Somewhat related: I've always enjoyed that the matrix multiplication algorithms with the best theoretical time complexity, are completely impractical for use on
by MaxBarraclough 8y ago
Somewhat related: I've always enjoyed that the matrix multiplication algorithms with the best theoretical time complexity, are completely impractical for use on real-world matrix multiplication problems.
Wikipedia describes why people use the Strassen algorithm in real-world implementations, despite its inferior asymptotic time complexity [0] :
> unlike the Strassen algorithm, it is not used in practice because it only provides an advantage for matrices so large that they cannot be processed by modern hardware.
[0] https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a...
- taeric 8y agoHad a fun discussion on that in this forum not long ago. https://news.ycombinator.com/item?id=17891360 https://news.ycombinator.com/item?id=17891360 Basically, I was hoping some of the optimized methods were competitive nowdays. Spoiler, still not practical. :(