News for hackers. Stuff that matters.
Re:Discovering faster matrix multiplication algorithms with ... by svnt on Wednesday October 05, 2022 @11:48AM (#33097086)
The big claim turns out to be a little overstated. The claim:

> AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago.

reduces to:

> AlphaTensor discovers algorithms that outperform the Strassen-square algorithm, which is a fast algorithm for large square matrices31,32. Although the discovered algorithm has the same theoretical complexity as Strassen-square, it outperforms it in practice, as it is optimized for the considered hardware. Interestingly, AlphaTensor finds algorithms with a larger number of additions compared with Strassen-square (or equivalently, denser decompositions), but the discovered algorithms generate individual operations that can be efficiently fused by the specific XLA33 grouping procedure and thus are more tailored towards the compiler stack we use. The algorithms found by AlphaTensor also provide gains on matrix sizes larger than what they were optimized for. Finally, Fig. 5c shows the importance of tailoring to particular hardware, as algorithms optimized for one hardware do not perform as well on other hardware.

So they improved on Strassen’s 50-year-old algorithm by optimizing it for hardware that has only existed for a few years and de-optimizing it for human use? There is so much cool stuff here without claiming to do something you really didn’t.

Re:Discovering faster matrix multiplication algorithms with ... by boole1854 on Wednesday October 05, 2022 @12:15PM (#33097434)
This is not a correct summary of the results of the paper.

First, you cut out the initial part of the sentence about improving on Strassen's two-level algorithm. Here is the complete sentence:

> Particularly relevant is the case of 4 × 4 matrices in a finite field, where AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago.

That is, note that the improvement cited in the latter part of the sentence is for the 4 x 4 matrix case.

But then your next quote is not in reference to 4 x 4 matrices. That is, for larger matrix sizes, the best algorithm AlphaTensor discovered had the same theoretical complexity as Strassen-square, but better performance.

EDIT: my next comments are confused and best ignored. See reply from pxx below.

For the 4 x 4 matrix case, the theoretical complexity of AlphaTensor's algorithm was O(N^2.778) compared with the Strassen algorithm's complexity of O(N^2.8074), which is an improvement.

Re:Discovering faster matrix multiplication algorithms with ... by pxx on Wednesday October 05, 2022 @12:22PM (#33097518)
what, no, you have this all wrong. the complexity of multiplying two 4x4 matrices is clearly constant. the important thing about the constant, however, is that you can use this primitive on the block matrices recursively to possibly improve the asymptotic complexity.

the complexity improvement in this paper is for arithmetic in Z_2 (modular arithmetic over single bits). in standard arithmetic, there is no asymptotic complexity improvement but the developed algorithms involve more efficiently fusible[0] operations, which is useful for the target hardware.

[0] ed: this used to read 'with fewer multiplications,' which is clearly wrong: fewer multiplications would lower complexity. Interestingly, the discovered algorithm seems to have a larger number of additions, but still runs faster.

Re:Discovering faster matrix multiplication algorithms with ... by ColinWright on Wednesday October 05, 2022 @01:08PM (#33098259)
I thought that savings on the number of multiplications leads to savings in complexity. For example, multiplying 2x2 matrices using 7 multiplications instead of 8 gives an improvement in complexity.

See my comment here: https://news.ycombinator.com/item?id=33098192

It's possible that my understanding is completely wrong, but your comment is at odds with my other reading, so it would be useful to get some clarification.

Re:Discovering faster matrix multiplication algorithms with ... by sdenton4 on Wednesday October 05, 2022 @01:25PM (#33098484)
This is correct, as I understand it.

Most complexity measures are defined in terms of asymptotic behavior, so any specific finite algorithm has 'constant' complexity. This is an obviously unhelpful bit of pedantry in the theory side.

In fact, it's as you say; we can compute a 'raw' complexity for a finite operation (eg, raw count of arithmetic ops), and then use that operation as a primitive to create an algorithm with an asymptotic complexity which depends directly on the finite operation's 'raw' complexity.

(complexity theory, and specifically for matrix multiplication, is a great example of metrics becoming targets becoming bad incentives, a la Goodhart's Law. The so-called best algorithms are 'galactic' and therefore of no use to anyone. There's some fuzzy-headed hope that one day the people chasing the big-O exponent metric will come up with something practically useful, buuuuuut... you actually gotta work practical problem to solve the practical problem, and that requires different metrics. This seems to be what's motivating the work under discussion here.)

Re:Discovering faster matrix multiplication algorithms with ... by pxx on Wednesday October 05, 2022 @01:32PM (#33098596)
sorry; whoops, I don't know why I said multiplications there. I somehow thought the "more additions" somehow meant "fewer multiplications," but no, it's just "more additions but faster performance on target." edited.

your other comment notes that for some shapes, even in standard arithmetic, they have found algorithms with fewer multiplications than best-known. but those don't seem to extend to an algorithm with better asymptotic complexity for multiplying general matrices. otherwise I'd assume they'd claim them :)

Re:Discovering faster matrix multiplication algorithms with ... by boole1854 on Wednesday October 05, 2022 @12:27PM (#33097570)
You are correct. I will edit.
Re:Discovering faster matrix multiplication algorithms with ... by a-dub on Wednesday October 05, 2022 @12:46PM (#33097921)
if you're in gf2 on a traditional cpu and care about wall clock time, i start to wonder how something like simd xors and parity would compare...
Re:Discovering faster matrix multiplication algorithms with ... by Nihmie on Wednesday October 05, 2022 @03:15PM (#33100034)
To be pedantic about this complexity estimate for the 4 x 4 case, both of them reduce to a O(1). If N == 4, it's a constant, so we have O(4^2.778) == O(4^2.8074) == O(1).

Talking about scaling for a problem that has no scaling factor is a bit odd.

Re:Discovering faster matrix multiplication algorithms with ... by est31 on Wednesday October 05, 2022 @05:55PM (#33101680)
Yeah the paper uses O notation for complexity, but never when N is constant. For constant N and M, the paper uses the number of scalar multiplication operations performed as complexity measure. According to Figure 3, their algorithm has decreased the best known value from 49 to 47 for 4x4 matrices, and from 98 to 96 for 5x5 matrices (as well as some further state of the art improvements).
Re:Discovering faster matrix multiplication algorithms with ... by vlovich123 on Wednesday October 05, 2022 @04:04PM (#33100625)
If you have to process many such matrices, you’re not at O(1). I would imagine that’s what the O is referring to in this case.
Re:Discovering faster matrix multiplication algorithms with ... by cochne on Wednesday October 05, 2022 @05:18PM (#33101352)
If you look at it that way then any algorithm is just o(n) where n is the number of matrices. O does not care about constant factors
Re:Discovering faster matrix multiplication algorithms with ... by vlovich123 on Friday October 07, 2022 @02:57PM (#33125478)
There's a better explanation here: https://fgiesen.wordpress.com/2022/10/06/on-alphatensors-new...

This is for matrix multiplication where elements are themselves 4x4 matrices. So yes, indeed this is about multiplying many many 4x4 matrices where N is the size of the outer matrix.

Re:Discovering faster matrix multiplication algorithms with ... by throwawaymaths on Wednesday October 05, 2022 @08:48PM (#33103049)
To be pedantic, paper is very clear that O is calculated after decomposing arbitrarily large matrices to 4x4s.
Re:Discovering faster matrix multiplication algorithms with ... by skybrian on Wednesday October 05, 2022 @12:22PM (#33097524)
Isn’t multiplying two 4x4 matrices a finite problem? What does big O complexity mean in that case?
Re:Discovering faster matrix multiplication algorithms with ... by adgjlsfhk1 on Wednesday October 05, 2022 @12:35PM (#33097719)
any fixed size multiplication algorithm has a corresponding general algorithm where you recursively divide a matrix into blocks and treat each block as an element. for any nxn algorithm that takes k multiplications, this yields a general algorithm with runtime n^log_n(k)
Re:Discovering faster matrix multiplication algorithms with ... by Rioghasarig on Wednesday October 05, 2022 @12:55PM (#33098078)
My understanding of this situation is that they found a way to multiply 4x4 matrices that requires fewer multiplications than Strassen's . This implies that that can generalize to a way to multiply n x n matrices with a better theoretical complexity than Strassen's algorithm.
Re:Discovering faster matrix multiplication algorithms with ... by dgacmu on Wednesday October 05, 2022 @12:19PM (#33097475)
In Z_2 - modular matrix multiplication, not conventional matrix multiplication. And in this case, modular over what I assume is GF(2), i.e., single bits.
Re:Discovering faster matrix multiplication algorithms with ... by aaaaaaaaaaab on Wednesday October 05, 2022 @01:06PM (#33098236)
Modular multiplication over GF(2)… also known as AND?
Re:Discovering faster matrix multiplication algorithms with ... by chabons on Wednesday October 05, 2022 @12:14PM (#33097414)
Maybe I'm mis-reading the paper, but my interpretation was that the algorithm discovered using a reward which scales with HW performance matches the theoretical complexity of Strassen, but is more performant on the HW.

They also identified algorithms which do fewer matrix multiplications than Strassen, improving the lower bound of matrix multiplies required (They highlight this in Fig 3).

In that light, I thought their claim was fair. They've discovered (different) algorithms which are both theoretically and practically better than Strassen's.

Re:Discovering faster matrix multiplication algorithms with ... by dekhn on Wednesday October 05, 2022 @11:53AM (#33097154)
That's the DeepMind modus operandi- and why they publish in Nature. It's in their best interest to claim as much covered ground as possible so they can keep working towards their end-goal. But most people who read Nature already know that results in that journal are overhyped. You just have to apply a specific prior/translator when you read their papers.
Re:Discovering faster matrix multiplication algorithms with ... by noobermin on Wednesday October 05, 2022 @12:07PM (#33097344)
This really is a depressingly true sentiment. Nature is both the most important publication but so often, the big shots publish overhyped stuff there that doesn't deserve it but get away with it since they are bigshots. Underscore here for another piece of evidence of the dysfunction in science.
Re:Discovering faster matrix multiplication algorithms with ... by brutusborn on Wednesday October 05, 2022 @12:28PM (#33097585)
I don't doubt the sentiment is true, but hasn't this kind of science always been this way? By that I mean authors inflating the importance of their work; everyone wants to be seen as having the biggest breakthroughs.

When I think of dysfunction in 'science' I usually think of unfalsifiable hypothesis, the repeatability crisis in Psychology, p-hacking in Medicine, misuse of statistical methods in Economics and other epistemic issues, but I don't think of exaggerations like this.

Re:Discovering faster matrix multiplication algorithms with ... by dekhn on Wednesday October 05, 2022 @12:46PM (#33097923)
Scientists have long been self-promoters who desire that their theories become the dominant ones and they use many techniques to achieve this.

However, the trend towards maximizing the predicted outcomes of your research really took off during the human genomics project.

Re:Discovering faster matrix multiplication algorithms with ... by YorkshireSeason on Wednesday October 05, 2022 @12:56PM (#33098092)
I would imagine that it's the metrics universities and funding agencies apply in promotion decisions. For example, my (well-known) university decided to measure impact, and takes "Twitter engagement" as one proxy metric for impact -- against my explicit recommendations. I'll leave the consequences to everybody's imagination.
Re:Discovering faster matrix multiplication algorithms with ... by dekhn on Wednesday October 05, 2022 @01:05PM (#33098221)
Yes. In fact many scientists post to twitter but don't look at the replies (Emily Bender is an example) or even block you if you disagree with them. That's not engagement and I wonder what the dean would do about a promotion where the scientist just sort of blathered on twitter and had lots of followers, but wasn't actually providing any real scientific value (again, Emily Bender is an example).
Re:Discovering faster matrix multiplication algorithms with ... by YorkshireSeason on Wednesday October 05, 2022 @01:15PM (#33098363)
Deans typically lack detailed technical knowledge to evaluate candidates (not to mention time), they just go with the flow, and want to run the department smoothly.

I think the real mechanism is this: those who make the decision (those with the most power, i.e. those who bring in the most funding and can threaten to leave if they don't get their way) already know whom they want and they cherry-pick data, eg "impact" figures, to bolster their case. That enables the dean then to justify the decision in public with those cherry-picked figures ... (the dean can hardly say we are hiring X because otherwise top funding getter Y will leave)

I think Twitter is less important in STEM subjects than in social sciences or humanities, as STEM has more clearcut results.

Re:Discovering faster matrix multiplication algorithms with ... by brutusborn on Thursday October 06, 2022 @02:49AM (#33105217)
Any more info on the changes from the human genomics project?
Re:Discovering faster matrix multiplication algorithms with ... by adalacelove on Wednesday October 05, 2022 @02:59PM (#33099836)
> Scientists have long been self-promoters

The famous ones more than the rest, I guess. To my mind nevertheless comes Cavendish, my hero.

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.
Re:Discovering faster matrix multiplication algorithms with ... by throwawaymaths on Wednesday October 05, 2022 @01:05PM (#33098214)
No, they count multiplications, 47 vs 49 in the 4x4 case. This assumes that multiplications are the heavy lift relative to additions, memory moves, etc. this is not a bad assumption, and is hardware independent, although there are some proposed 'exotic' hardware solutions where addition and multiplication are equally difficult (via lookup table, limited to about 8-bit x 8-bit) or where addition is harder than multiplication (log space number systems) but I don't think these have been deployed
Re:Discovering faster matrix multiplication algorithms with ... by lifthrasiir on Wednesday October 05, 2022 @01:35PM (#33098651)
That assumption didn't age very well. In many if not most modern architectures multiplication still does take more cycles than addition but can have a higher throughput if scheduled well, and fused multiply-add can be as fast as a single multiplication, essentially giving a free addition.
Re:Discovering faster matrix multiplication algorithms with ... by throwawaymaths on Wednesday October 05, 2022 @01:43PM (#33098774)
> but can have a higher throughput if scheduled well

Unlikely to be true for matrix multiplications, which have well-defined data dependencies.

> and fused multiply-add can be as fast as a single multiplication, essentially giving a free addition.

Yes, this supports the assumption that multiplication is the heavy lift.

Re:Discovering faster matrix multiplication algorithms with ... by tlb on Wednesday October 05, 2022 @04:27PM (#33100875)
With sufficiently parallel hardware, you can do an entire mat4 * mat4 multiplication in 3 cycles. First do all 64 multiplications in parallel, then do 32 adds, then 16 adds to get the final answer.

For operations in GF(2) where they claim a result, a multiply is just an AND gate and an add is an XOR gate. So the fully parallel hardware version is 64 AND gates and 48 XOR gates, with a total gate delay of 3. This is a trivial amount of hardware and could easily be an instruction in some alternate universe where it was useful.

Re:Discovering faster matrix multiplication algorithms with ... by klyrs on Wednesday October 05, 2022 @06:02PM (#33101759)
You missed the part where the "4x4 matrix multiplication" refers to multiplication of NxN matrices logically partitioned into sixteen blocks of size (N/4)x(N/4), done recursively.
Re:Discovering faster matrix multiplication algorithms with ... by letitgo12345 on Wednesday October 05, 2022 @01:29PM (#33098555)
I think they find a N^2.778 complexity algorithm (obtained by applying their 4x4 discovered algorithm recursively) so this is not correct.
Re:Discovering faster matrix multiplication algorithms with ... by ColinWright on Wednesday October 05, 2022 @01:04PM (#33098206)
How can I reconcile your comment here with the comment in https://news.ycombinator.com/item?id=33098192 ??
Re:Discovering faster matrix multiplication algorithms with ... by Ar-Curunir on Wednesday October 05, 2022 @02:14PM (#33099168)
You’re wrong. They discovered an algorithm with fewer multiplications for 4x4 matrices.

They also discovered better algorithms for other dimensions.

Re:Discovering faster matrix multiplication algorithms with ... by johndfsgdgdfg on Wednesday October 05, 2022 @08:27PM (#33102921)
What do you expect from an ad company? Not the truth.
Re:Discovering faster matrix multiplication algorithms with ... by oittaa on Thursday October 06, 2022 @05:18AM (#33106219)
Hey, you haven't chosen the betting site yet. Which one do you prefer?

https://news.ycombinator.com/item?id=33102761