News for hackers. Stuff that matters.
Re:How to write efficient matrix multiplication by sampo on Sunday May 27, 2018 @03:10PM (#17168549)
> Those sub-cubic algorithms require the matrix to be very-very-very large to recoup the extra constant costs associated with them.

Wikipedia disagrees:

"In practice, Strassen's algorithm can be implemented to attain better performance than conventional multiplication even for small matrices, for matrices that are not at all square, and without requiring workspace beyond buffers that are already needed for a high-performance conventional multiplication."

https://en.wikipedia.org/wiki/Strassen_algorithm

Re:How to write efficient matrix multiplication by danmg on Sunday May 27, 2018 @03:36PM (#17168709)
That's not what I learned in grad school when I took a class on this.
Re:How to write efficient matrix multiplication by sdenton4 on Sunday May 27, 2018 @03:45PM (#17168761)
I used to use Atlas quite a bit, which effectively benchmarks your CPU and memory configuration at installation time to empirically determine where to switch from 'small n' algorithms to asymptomatically optimal algorithms, like Strassen.

Of course, if you only some resources into optimizing the cubic time version, Strassen will look slow by comparison. Better we take a serious look at both and empirically figure out where the trade off point is...

Re:How to write efficient matrix multiplication by danmg on Sunday May 27, 2018 @05:55PM (#17169303)
Yes atlas is good.

For small, dense n you're not going to beat the cubic algorithm. This is the most common case in a lot of applications.

For sparse n, use a sparse version of the cubic algorithm. For large dense n, those sub-cubic algorithms might be better. Here n would have to be so large that you'd have to factor in the cost of doing it out of core.

Re:How to write efficient matrix multiplication by sampo on Sunday May 27, 2018 @03:58PM (#17168828)
Wikipedia refers to this paper from 2016.

https://dl.acm.org/citation.cfm?id=3014983