News for hackers. Stuff that matters.
Re:Discovering faster matrix multiplication algorithms with ... by atty on Wednesday October 05, 2022 @12:21PM (#33097494)
On the other hand, real world performance is really the only useful metric for matrix multiplication. I don’t really care about the theoretical performance, or the number of operations. Not disagreeing with your take that the claim is grandiose, just pointing out that finding a generalizable way to automate the improvement of what is almost certainly the most important mathematical operation a computer can do is worth some attention. It also suggests other mathematical operations could be improved this way as well - potentially algorithms that haven’t gotten as much theoretical or practical attention as matrix multiplication. With all that said, they even point out that other people have worked on this before using other optimization strategies. I’d guess they got into Nature either by using the Deepmind name, because Nature really loves reinforcement learning because it’s a cool topic that draws views, or because they’re the first group to find their algorithm leads to real improvements. (Probably a mixture of all three, I’d guess)
Re:Discovering faster matrix multiplication algorithms with ... by dekhn on Wednesday October 05, 2022 @01:12PM (#33098323)
Science proceeds at the rate by which linearly larger matrices can be decomposed in less than exponential time.
Re:Discovering faster matrix multiplication algorithms with ... by matheusd on Wednesday October 05, 2022 @02:33PM (#33099470)
This is excellent! You should make a T-Shirt with this quote on it!
Re:Discovering faster matrix multiplication algorithms with ... by throwawaymaths on Wednesday October 05, 2022 @01:09PM (#33098271)
> the number of operations

This is a very good proxy for actual real world speed. It's pretty much "as good as it gets" for most straight computational tasks, though sometimes memory movement is your real bottleneck.

Re:Discovering faster matrix multiplication algorithms with ... by sdenton4 on Wednesday October 05, 2022 @01:29PM (#33098550)
This is questionable...

The 'best' algorithms for matrix multiplication are galactic algorithms that provide no actual benefit. Raw operation counts are a good proxy for speed, but the big-O complexity that people actually chase hasn't been especially helpful for this problem in the last twenty+ years.

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

Re:Discovering faster matrix multiplication algorithms with ... by throwawaymaths on Wednesday October 05, 2022 @01:35PM (#33098644)
Probably the most common matrix multiplication is (nx9) x (9xm) (9 = 3x3 cells from a convnet) . If you can optimize the shit out of those you might be in business for something interesting.

Though to be honest the real slow step in machine learning is training and the slow step in training is the outer product of two matrices.... I don't believe there is an algorithmic way out of that one.

For non-ml/non-GF purposes, you might also worry about numerical stability of these matrix multiplications, which is not addressed in this paper.

Re:Discovering faster matrix multiplication algorithms with ... by a1369209993 on Wednesday October 05, 2022 @05:41PM (#33101557)
> and the slow step in training is the outer product of two matrices.... I don't believe there is an algorithmic way out of that one.

Well, there are several, but the obvious ones tend to require strange or unrealistic assumptions about the hardware. The most obvious such assumption, IMO, being that the hardware is arranged in 3D space in a manner roughly analogous to a human brain, which tends to be at odds with the common practice of mostly-planar photolithography, and with the preference to be able to change the network topology experimentally without building new hardware.

Re:Discovering faster matrix multiplication algorithms with ... by fulafel on Wednesday October 05, 2022 @02:22PM (#33099272)
It's become a much worse proxy since the memory wall.
Re:Discovering faster matrix multiplication algorithms with ... by psychphysic on Wednesday October 05, 2022 @12:28PM (#33097596)
Surely theoretical improvement begets real world, especially in the context of highly specialised hardware.

It was with theoretical performance improvement that motivated the creation of SIMD and led to real world speed ups.

Re:Discovering faster matrix multiplication algorithms with ... by fulafel on Wednesday October 05, 2022 @04:04PM (#33100622)
It's interesting how both SIMD and big-o have had so different reasons for being of limited but still significant relevance.

SIMD, and vector processors like it was called in the 70s, delivered practical speedups in simple benchmarks right away but most applications dont't take advantage because of SW engineering reasons. Whereas big-O improvement ignores important components of performance per unit of time (memory access and constant factors) and is purely theoretical in an essential sense.

Re:Discovering faster matrix multiplication algorithms with ... by chrchang523 on Wednesday October 05, 2022 @01:49PM (#33098855)
Sometimes. In the case of matrix multiplication, there is a pretty large backlog of "galactic algorithms" going down to ~O(n^2.373) that haven't yet led to real-world improvements. Strassen's ~O(n^2.807) algorithm is only considered over the basic O(n^3) strategy for n>1000.
Re:Discovering faster matrix multiplication algorithms with ... by HarHarVeryFunny on Wednesday October 05, 2022 @04:05PM (#33100637)
Winograd O(n^2.37) is a win for 3x3 convolutions in cuDNN, so it can be implemented efficiently.
Re:Discovering faster matrix multiplication algorithms with ... by chrchang523 on Wednesday October 05, 2022 @04:46PM (#33101060)
My understanding is that the Winograd minimal filtering algorithms used in cuDNN are different from the O(n^2.37) Coppersmith-Winograd-descended matrix multiplication algorithms. But I acknowledge that these can be considered cousins, produced by the same line of research.
Re:Discovering faster matrix multiplication algorithms with ... by HarHarVeryFunny on Wednesday October 05, 2022 @05:01PM (#33101210)
I'm pretty sure there's no difference. It does seem to be pretty hard to turn the theoretical win into a practical one - the GPU kernel needs to be coded extremely efficiently to match the underlying hardware. AFAIK it's only a win for 3x3 - maybe for one other size too. Originally Winograd wasn't supported by cuDNN on NVidia's Tensor Cores (matmul-specific hardware on more recentish GPUs), vs CUDA cores, but a Google search seems to indicate it can be done - not sure if that's in cuDNN though.
Re:Discovering faster matrix multiplication algorithms with ... by taeric on Wednesday October 05, 2022 @01:12PM (#33098325)
Not necessarily. In particular, this could have slower growth, but still higher cost on normal workloads.