New breakthrough brings matrix multiplication closer to ideal
quantamagazine.org
quantamagazine.org
AFAIK the current theoretical lower bound still is 2, so that’s only 600-ish more such steps to get there.
On the positive side, I don’t think anybody believes that 2 even remotely is a tight bound.
Not remotely close to 2.
What is the limit you would set for remotely close to 2?
It's not "still". It's trivial to prove that 2 is the lowest possible value. Simply because you can't even read all the inputs in less than n^2 operations. So it's a tight lower bound for sure.
Lots (well, relatively lots; this isn’t a research area with millions of practitioners) of people must have been looking at that problem ever since Strassen showed the exact value is less than 3 in 1969 (https://en.wikipedia.org/wiki/Strassen_algorithm), and there hasn’t been progress on moving that needle, so I doubt it’s even remotely easy, though.
Sorry, nothing substantial to add, I just got excited about it again
[1] I'm sure everyone who clicked the downvote button thought it was obvious, but not everyone here has that level of intuition about big-O analysis. This isn't a math forum, we're all hackers here, right?
New Bounds for Matrix Multiplication: From Alpha to Omega - https://news.ycombinator.com/item?id=39630949 - March 2024 (22 comments)
1. in general, algorithms tend to slow down on small problems in exchange for the asymptotic speedup -- so you probably don't want to use this algorithm for anything that fits in memory (or perhaps the solar system)
2. in specific, asymptotically fast matrix multiplication tend to be numerically unstable. So you probably don't want to use this algorithm unless you're working with infinite precision.
This is not necessary true and very much depend on specifics of an algo. Some improvements could be very applicable for quite normally sized tensors. For example, Winograd algorithm is quite often a routine choice for 3x3xc convolutions.
> 2. in specific, asymptotically fast matrix multiplication tend to be numerically unstable.
This should be investigated in each particular case of an algorithm, but numeric stability is indeed a major concern for a practitioner. I skimmed very superficially through the article but didn't notice mentions of that.
These algorithms reduce the number of multiplies, but seem to increase the total number of floating point ops (including both adds and multiplies), unless I'm mistaken.
(1) Pre-process an nxn matrix m into f(m). Any transformation is allowed, but to work well on all matrices and input vectors it's not possible to rely solely on compression techniques (random sampling, low-rank+sparse approximation, ...).
(2) Compute an approximation of m@v via some computation g(f(m), v) in less than O(n^2) time (ideally being able to trade off accuracy for speed). Above a certain performance threshold, this necessarily means you only use a part of f(m) for any one vector v.
There's a zero-error O(n) solution that computes a hash table of all possible matrix-vector products, so I'll be picky and add the constraint that pre-processing time/space are "reasonable".
1 x
0 1
Then you can do basic arithmetic with 0 resources.
The answer is quite a lot in computing terms, matrix multiplication is used everywhere, most notably at the moment, neural networks use almost entirely matrix multiplication, so their power consumption would drop almost entirely, and correspondingly we could scale them up enormously, your phone could run GPT5 locally as long as it had the storage space, high fidelity computer vision everywhere would become trivial, Google Glass might even become useful.
Previously very limited engineering simulations like weather forecasting would improve by leaps and bounds.
Basically everything would change all at once because we'd have effectively made p = np, any problem you can turn into a matrix multiplication (so basically most maths problems) would become solvable.
At the moment we use hardware like GPU's and TPU's in the case of AI to make matrix multiplication much quicker and the companies that make them have recently become some of the biggest in the world because it's so important to everything we do now to be able to multiply matrices quickly.
So the better question to ask is: What happens if we find a practical algorithm (and a theoretical approach) that lets us do matmul in only n^2 time? And the answer is - well, some important things get faster and we're able to solve larger problems in things like optimization, simulation, deep learning, etc., or save a lot of time and money doing them.
We'd go from about n^2.8 to n^2, which, let's say for a 1M x 1M matrix, is about 64k times faster. That's really nice. But the speedup for more common sized matrices is smaller - 256x faster for a 1024x1024 matrix.
It would be a very important thing that would cause us to re-examine the use of matrix multiplication as a primitive for more things, and would have very important practical implications - and at the same time, would also kind of look like 15 years of Moore's law, not that we're guaranteed to have 15 years of that. So, "big" but not necessarily "totally reshape the world".