How AI Discovered a Faster Matrix Multiplication Algorithm

Researchers at Google research lab DeepMind trained an AI system called AlphaTensor to find new, faster algorithms to tackle an age-old math problem: matrix multiplication. Advances in matrix multiplication could lead to breakthroughs in physics, engineering and computer science.

AlphaTensor quickly rediscovered - and surpassed, for some cases - the reigning algorithm discovered by German mathematician Volker Strassen in 1969. However, mathematicians soon took inspiration from the results of the game-playing neural network to make advances of their own.

Correction: At 2:53 in the video, the text previously read "67% less" but has been changed to "67%" for accuracy.

00:00 What is matrix multiplication?
01:06 The standard algorithm for multiplying matrices
02:06 Strassen's faster algorithm for faster matrix multiplication methods
03:55 DeepMind AlphaGo beats a human
04:28 DeepMind uses AI system AlphaTensor to search for new algorithms
05:18 A computer helps prove the four color theorem
06:17 What is a tensor?
07:16 Tensor decomposition explained
08:48 AlphaTensor discovers new and faster faster matrix multiplication algorithms
11:09 Mathematician Manuel Kauers improves on AlphaTensor's results

#math #AlphaTensor #matrices

[alexanderkvenvolden]

So to make matrix multiplication more efficient, they used machine learning, which relies heavily on matrix multiplication. Very cool!

[sheevys]

One cool thing from tha paper which didn't make it to the video was that instead of using number of multiplications as your cost function, one can use the actual timings from running each algorithm. This allows to find fast multiplication algorithm which is tailored for the device it's running on. Interestingly, they showed that indeed for different hardware platforms, different algorithms performed better.

[Wooksley]

I finished university 4 years ago and I still get nightmares about my diploma being revoked because they’ve discovered that I failed linear algebra exam. Doing matrix multiplication by hand is a literal nightmare for me.

[ABaumstumpf]

For matrix-multiplications Strassen is the best overall - works for any size and any form of matrices. But there are of course faster methods for specific cases. There are algorithms that are faster for where large matrices, that are better for diagonalised matrices etc

They found an algorithm for matrices only containing 1 and 0 that is slightly faster - single-digit percentage faster. It is an achievement and does help, but the bigger benefit might just be that with specialised hardware it can use fewer multiplication-units - thus less power.

[QuantenMagier]

I read the corresponding papers and this is a pretty good recap video on the topic. Kudos for visualizing the algorithms in an understandable way and even giving some background information from the researchers! 🧑‍🎓

[alphalunamare]

I devised an algorithm in 1977 that utilised 24 multiplications and 69 additions for the 3x3 case but didn't get much further as it was equivalent to Strassen's in the 2x2 case. I did it with pencil and paper. After seeing this video I don't feel so bad now about my failure :-)

[RepChris]

I mean _technically_ weve had "faster" algorithms than the stassen one for quite a bit. Were down from the factor of ~2.7 to ~2.37 for very large matrices. Although an actually usable algorithm thats faster even in the relatively special cases is always nice to see

[KnakuanaRka]

The way you described the tensor decomposition problem as a game of removing tensors from the original to reduce it to all zeros as fast as possible, and how you showed it with the Strassen example, reminds me a lot of the Lights Out game where you press a light to flip it and all adjacent to make all the lights dark. The moves in tensor decomposition are a lot more complex of course, but seeing it as a game makes a lot of sense.

[silentblackhole]

I didn't follow along with some of the more detailed parts but over all found it to be really interesting. Nice work to everyone involved in this directly or otherwise.

[OmenaMC]

Bruh ai literally made itself faster 💀💀💀

[Dismythed]

Never explained how AT achieved the matrix calculations with fewer steps than previous (47 to 45 or 96 to 95).

[LordofDorkness]

Minor error at 2:53. Shouldn't it just say 67% rather than 67% less?

[OtakuSanel]

matrix math is just one of those things that while more efficient equations might be good on the theory side of things, there is far more gains from specialized hardware to do that kind of math. if something has 8 vs 7 multiplications might be a factor if you are forced to do it consecutively, when you have hardware that does it all at once one more "lane" of computation for that 8th figure is a moot point. Back in the day there used to be math co-processors and we came back full swing where now the gpu IS the math co-processor once more with things like cuda and tensor cores that are specifically designed for that kind of math. The big question is, what other kind of specialized hardware would be of high value and implement that rather than pushing the limits of math theory to find efficiency.

[GrimJerr]

The power of AI isn't intelligence, it is a feature of Iteration.

[Alexandre-uroi]

For the sake of completness, in practical applications one should keep in mind that reducing the number of basic operations is not the main bottelneck for matrix multiplication efficiency, moving data is (bus 500Mh, cpu 1-2Ghz). However, without new ideas on this (last not understood) basic operation (polynomial, integer multiplication is mastered), brute computer force (cleverly used in the present case) is welcome.

[Techmagus]

To explain the Alphatensor result it would be better to show and explain the Karazuba algorithm as Alphatensor found something similiar for 4x4 to Karazuba for 2x2. Sure Strassen is beating Karazuba on 2x2 so it should be mentioned, but for the didactic of the solution Karazuba is giving more insight to the result.

[miloweising]

Okay but do we know yet if this type of multiplication algorithm will work in any context other than Z/2Z? It is not surprising to think that there are extra tricks to multiplying matrices in Z/2Z that one could use which are useless over the reals.

[rashid]

Math just goes over my head, but it is cool that we can automate the trial-and-error aspect of mathematical models.

[cbunix]

For very large matrices you can get an easy 40% speed-up over the naive algorithm if you order the multiplication and addition operations in a cache coherent order. I'm skeptical would be faster than Strassen's though.

[cheesySamar]

Me who hasnt even graduated highschool watching video and reading all the comments/arguments like i know better