17
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
this post was submitted on 18 May 2025
17 points (100.0% liked)
TechTakes
2122 readers
278 users here now
Big brain tech dude got yet another clueless take over at HackerNews etc? Here's the place to vent. Orange site, VC foolishness, all welcome.
This is not debate club. Unless it’s amusing debate.
For actually-good tech, you want our NotAwfulTech community
founded 2 years ago
MODERATORS
Yes - on the theoretical side, they do have an actual improvement, which is a non-asymptotic reduction in the number of multiplications required for the product of two 4x4 matrices over an arbitrary noncommutative ring. You are correct that the implied improvement to omega is moot since theoretical algorithms have long since reduced the exponent beyond that of Strassen's algorithm.
From a practical side, almost all applications use some version of the naive O(n^3) algorithm, since the asymptotically better ones tend to be slower in practice. However, occasionally Strassen's algorithm has been implemented and used - it is still reasonably simple after all. There is possibly some practical value to the 48-multiplications result then, in that it could replace uses of Strassen's algorithm.
One thing that I couldn't easily figure out is what is the constant factor. If the constant factor is significantly worse than for Strassen, then it would be much slower than Strassen except for very large matrices.
Let's say the constant factor is k.
N should be large enough that N^((log(49)-log(48))/log(4)) > k where k is the constant factor. Let's say the difference in exponents is x, then
N^x > k
log(N)*x > log(k)
N > exp(log(k)/x)
N > k^(1/x)
So lets say x is 0.01487367169 , then we're talking [constant factor]^67 for how big the matrix has to be?
So, 2^67 sized matrix (2^134 entries in it) if Google's is 2x greater constant than Strassen.
That don't even sound right, but I double checked, (k^67) ^ 0.01487367169 is approximately k.
edit: I'm not sure what the cross over points would be if you use Google's then Strassen's then O( n^3 )
Also, Strassen’s algorithm works on reals (and of course, on complex numbers), while the new "improvement" reduces by 1 the number of real multiplications required for a product of two 4x4 complex-valued matrices.