3 ms·
Interestingly, given this blog post, i'm 100% sure that there are further improvements that can be made. To my knowledge, strassen's isn't actually used by most
by joshuamorton 9y ago
Interestingly, given this blog post, i'm 100% sure that there are further improvements that can be made. To my knowledge, strassen's isn't actually used by most high performance matrix libraries because the constants are too high that it outweighs the theoretical gains.
- jedbrown 9y agohttps://www.cs.utexas.edu/~jianyu/papers/sc16.pdf https://www.cs.utexas.edu/~jianyu/papers/sc16.pdf (paper) https://www.cs.utexas.edu/~jianyu/presentations/strassen_sc16.pdf https://www.cs.utexas.edu/~jianyu/presentations/strassen_sc1... (slides)
- joshuamorton 9y agoIf I'm reading page 65 of that presentation correctly, naive Strassen (what this person did) should be approximately 75% as fast as MKL on an 8 core machine for a 4Kx4K matrix, and even the improved algorithm outlined in the paper is only approximately equivalent, and I wouldn't call it "Strassen's". I stand by what I said (although that paper was a cool read!)
- jedbrown 9y agoSo ABC Strassen (one of the variants in the paper) is crossing over at 4000x4000 on 10 cores and ahead on fewer cores. I shared this as the current state of performance engineering for Strassen-like algorithms. It offers modest benefits in more practical regimes than the conventional wisdom. I agree that many applications of dense matrices do not benefit.