Matrix multiplication is at the heart of many machine learning breakthroughs, and it just got faster—twice. 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.
Matrix multiplication, which involves multiplying two rectangular arrays of numbers, is often found at the heart of speech recognition, image recognition, smartphone image processing, compression, and generating computer graphics. Graphics processing units (GPUs) are particularly good at performing matrix multiplication due to their massively parallel nature. They can dice a big matrix math problem into many pieces and attack parts of it simultaneously with a special algorithm.
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.
Going from 49 steps to 47 doesn’t sound like much, but when you consider how many trillions of matrix calculations take place in a GPU every day, even incremental improvements can translate into large efficiency gains, allowing AI applications to run more quickly on existing hardware.
When math is just a game, AI wins
AlphaTensor is a descendant of AlphaGo (which bested world-champion Go players in 2017) and AlphaZero, which tackled chess and shogi. DeepMind calls AlphaTensor “the “first AI system for discovering novel, efficient and provably correct algorithms for fundamental tasks such as matrix multiplication.”
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:
In this game, the board is a three-dimensional tensor (array of numbers), capturing how far from correct the current algorithm is. Through a set of allowed moves, corresponding to algorithm instructions, the player attempts to modify the tensor and zero out its entries. When the player manages to do so, this results in a provably correct matrix multiplication algorithm for any pair of matrices, and its efficiency is captured by the number of steps taken to zero out the tensor.
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.”
Tech progress builds off itself, and with AI now searching for new algorithms, it’s possible that other longstanding math records could fall soon. Similar to how computer-aided design (CAD) allowed for the development of more complex and faster computers, AI may help human engineers accelerate its own rollout.