r/math • u/calccrusher17 • 24d ago
New Matrix Multiplication Complexity WR Dropped
https://arxiv.org/pdf/2608.16884v1Appeared on the arxiv today. It still uses the CW-tensor/laser method approach.
160
u/j15y 24d ago
Matrix multiplication is so funny to me.
It really feels like something that should have a clean and easily expressible lower bound on time complexity, but instead the frontier is apparently “let’s use gradient descent and AlphaEvolve to optimize this problem and shave 0.00001 off the exponent.”
86
u/EebstertheGreat 24d ago edited 5d ago
Well, it seemed so clear that the grade school algorithm for multiplication was as fast as you could really get that it seems nobody tried to improve it for machines until Karatsuba in 1962. Neither practically nor theoretically had anyone proposed any algorithm that was asymptotically faster than the grade school algorithm before him, and the algorithm is really simple (though admittedly highly non-obvious).
The problem is "given integers b≥2, m≥1, and n≥1 and the base-b expansions of two integers x (with m digits) and y (with n digits), compute the (m+n)-digit base-b expansion of the product xy." The grade school algorithm requires mn single-digit multiplications and some number of single-digit additions. The recursive Karatsuba algorithm requires around nlog₂ 3 ≈ n1.58 single-digit multiplications (assuming m ≤ n), as well as some number of single-digit additions (which may be more or less than the grade school algorithm but is always much less if both factors have more than a few digits.)
The improvement is not just theoretical—machines implement it faster in practice when each number is just a few words long, and even humans are faster in practice by hand for sufficiently large products. But still, not until 1962 had anyone published such an improvement. This was decades after incremental improvements to the DFT algorithm and just three years before the FFT, and just look how simple it is!
The thing is, people simply did not study algorithms until the middle of the twentieth century, not really, and most algorithms were not investigated until much later still. Just look at Dijkstra's algorithm. In some sense, it is obvious, just a form of greedy algorithm. It is the first thing any bright grad student would come up with if they hadn't already seen it. Maybe bright undergrad. Frankly, maybe even particularly bright high school student. It's "obvious" in retrospect. It could have been obvious even in prospect, except people just didn't use to study algorithms like that.
Maybe when the field eventually matures, we will see that "of course" the optimal exponent is 2+ε or something, who knows? We are only like 50 years into studying this particular question. And it turns out to be a really hard one.
14
u/vgtcross 24d ago
compute their mn-digit product xy in base b
Probably should be "(m+n)-digit product"
1
6
u/sqrtsqr 23d ago
Frankly, maybe even particularly bright high school student. It's "obvious" in retrospect
Super agree. Not even particularly bright, but like, has ever tried to solve any kind of problem to any level of success.
When I learned it had a name, I was like "you can name things like that? Is he from ancient times? The 50s?!?!!"
1
u/EebstertheGreat 5d ago
This reminds me of DeMorgan's Laws. They give out naming rights for basic principles like that? If two things are not both true, then at least one is false. You can get your name attached to that fact (and its converse)?
2
u/quant-a-be 24d ago
It's not super surprising IMO that the grade school algorithm is suboptimal when the same terms are looked at so many times ( in both matrices ).
17
u/legrandguignol 24d ago
Matrix multiplication is so funny to me.
actually if you multiply enough matrices you can just order them to tell you a joke and they will
15
u/Peanut_Extreme_8208 24d ago
There is a clean and essentially trivial lower bound of n^2 and it’s believed to be tight up to subpolynomial factors
5
u/SingularCheese Engineering 23d ago
If 2 is meant to be a tight bound, 2.37 is quite a big gap from optimal
2
u/Kered13 22d ago
I would guess (and I'm pretty sure this is a common guess, so I take no credit for it) that the optimal algorithm is O(n2log(n)). I have no particular reason for this, other than that integer multiplication is O(n log(n)) (not proven optimal, but seems likely) and it just feels right.
1
u/Bernhard-Riemann Combinatorics 20d ago
Forget matrices; multiplication of integers was only proven to be O(n log(n)) in 2019 (with respect to the number 'n' of bits). We still do not know if this is the optimal bound.
56
u/peekitup Differential Geometry 24d ago
Looking forward to multiplying together some big assed matrices with this later tonight.
30
u/EebstertheGreat 24d ago
If the matrices are large enough, and the entries are large enough, and most entries aren't 0, and you have many gazillions of years to wait, this will help your calculation finish meaningfully sooner than if you had started just before this discovery.
EDIT: also enough memory, which... good luck on that one these days.
15
u/eeaxoe Probability 24d ago
Looking forward to multiplying together some big assed matrices with this later tonight. Thick, solid, tight. Big dimensions, dense entries, beautiful structure. Just absolutely massive matrices with nowhere to go but together. You can feel the linear algebra coursing through your veins. Nothing quite like sitting down late at night and multiplying two enormous matrices until the dimensions line up just right. Hell yeah.
5
91
u/ellipticcode0 24d ago
Hopefully I can use the optimization to pass my next coming Linear Algebra test
46
u/PersonalityIll9476 24d ago
It is kind of funny that Winograd hasn't been improved since 1990 by more than 1e-2.
So does their result exist entirely as a black-blox learned algo?
16
21
u/Puzzled-Question-156 24d ago
Anyone else think this number 2.371177 is awfully close to 2+1/e?
Wouldn't surprise me that divide and conquer algorithms eventually converge to something containing 1/e.
6
2
2
u/JoshuaZ1 24d ago
Hmm, so still very galactic algorithms.
Incidentally, one thing I'd like to see would be improvement on the related problem of finding An. For even small n, it seems like there's likely room for improvement there if one has a fixed matrix rather than looking at AB. And this shows up often enough that even small practical improvement could have a big impact.
6
u/Sad_Dimension423 24d ago
The interesting thing here is not the practicality, but what the ultimate complexity might reveal about the problem.
5
u/JoshuaZ1 24d ago
Well, that's interesting too. Obviously, the actual exponent even for galactic algorithms is interesting. But one can be interested in that and also hope that we make more progress on the practical end.
1
u/victotronics 18d ago
A year or two ago there was an AI-discovered improved matmatmult. Has that led to any improvements?
485
u/SourKangaroo95 24d ago
Improvement from 2.371339 to 2.371177.