3 ms·

What will happen to the world if we found a way to calculate matrix multiplication that uses 0s time and 0 resource?

vouaobrasil 3y ago
Well, since matrix multiplication also contains regular multiplication (multiplication of 1x1 matrices) and addition (multiplication of 2x2 matrices of the form 1 x 0 1 Then you can do basic arithmetic with 0 resources.
faceplanted 3y ago
Well, 0 isn't really possible, but assuming you're just asking "What would the impact be on the world if me made matrix multiplication trivial" in the same way that people ask what making a room temperature superconductor would do for us. 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.
dgacmu 3y ago
We would have broken some fundamental laws, because to multiply two n x n matrices, it takes n^2 time to write down the answer. 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".

Well, since matrix multiplication also contains regular multiplication (multiplication of 1x1 matrices) and addition (multiplication of 2x2 matrices of the form 1 x 0 1 Then you can do basic arithmetic with 0 resources.

faceplanted 3y ago

Well, 0 isn't really possible, but assuming you're just asking "What would the impact be on the world if me made matrix multiplication trivial" in the same way that people ask what making a room temperature superconductor would do for us. 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.

dgacmu 3y ago

We would have broken some fundamental laws, because to multiply two n x n matrices, it takes n^2 time to write down the answer. 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".