Last week, DeepMind announced it discovered a more efficient way to perform matrix multiplication, conquering a 50-year-old record. This week, two Austrian researchers at Johannes Kepler University Linz claim they have bested that new record by one step. Ars Technica reports: In 1969, a German mathematician named Volker Strassen discovered the previous-best algorithm for multiplying 4×4 matrices, which reduces the number of steps necessary to perform a matrix calculation. For example, multiplying two 4×4 matrices together using a traditional schoolroom method would take 64 multiplications, while Strassen’s algorithm can perform the same feat in 49 multiplications. Using a neural network called AlphaTensor, DeepMind discovered a way to reduce that count to 47 multiplications, and its researchers published a paper about the achievement in Nature last week.
To discover more efficient matrix math algorithms, DeepMind set up the problem like a single-player game. The company wrote about the process in more detail in a blog post last week. DeepMind then trained AlphaTensor using reinforcement learning to play this fictional math game — similar to how AlphaGo learned to play Go — and it gradually improved over time. Eventually, it rediscovered Strassen’s work and those of other human mathematicians, then it surpassed them, according to DeepMind. In a more complicated example, AlphaTensor discovered a new way to perform 5×5 matrix multiplication in 96 steps (versus 98 for the older method).
This week, Manuel Kauers and Jakob Moosbauer of Johannes Kepler University in Linz, Austria, published a paper claiming they have reduced that count by one, down to 95 multiplications. It’s no coincidence that this apparently record-breaking new algorithm came so quickly because it built off of DeepMind’s work. In their paper, Kauers and Moosbauer write, “This solution was obtained from the scheme of [DeepMind’s researchers] by applying a sequence of transformations leading to a scheme from which one multiplication could be eliminated.”
Read more of this story at Slashdot.