Hacker News Reader

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.

View on HN

https://www.cs.utexas.edu/~jianyu/papers/sc16.pdf (paper) https://www.cs.utexas.edu/~jianyu/presentations/strassen_sc1... (slides)

If 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!)

So 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.

Reply on news.ycombinator.com