Why Solving For Efficiency of Matrix Multiplication Such A Big Deal In Computing

You must have come across matrix multiplication in school textbooks. But did you know how relevant it is in every aspect of our daily lives, from processing images on our phones and recognising speech commands to generating graphics for computer games?  

It is at the core of nearly everything computational.

With DeepMind’s latest release AlphaTensor, an AI system, researchers shed light on a 50-year-old fundamental mathematics question of finding the fastest way to multiply two matrices.

“AlphaTensor discovered algorithms that are more efficient than state-of-the-art for many matrix sizes. Our AI-designed algorithms outperform human-designed ones, which is a major step forward in the field of algorithmic discovery,” DeepMind said in a statement.

The advancement is an extension of AlphaZero, a single system that mastered board games (Chess, Go and Shogi) from scratch without human inputs. Moreover, the research reveals that AlphaZero is a powerful algorithm that can be extended beyond the domain of traditional games to help solve open problems in mathematics.

The problem at hand

Matrix multiplication is one of the simplest forms of mathematics but gets intensely complex when applied in the digital world. Anything that can be solved numerically—from predicting the weather to compressing data—typically uses matrices. For instance, you can read this article on your screen because its pixels are represented as a grid, and they refresh with new information faster than your eyes can track. 

Despite its omnipresent nature, the calculation is not very well understood. Moreover, nobody knows a quicker method of solving the problem because there are infinite ways to do so. 

DeepMind’s gameplan

Breakthroughs in machine learning have helped researchers right from creating art to predicting protein structures. Increasingly, researchers are now using algorithms to become its own teacher and correct the flaws.

The DeepMind researchers did what they do best—making AIs champions at games.

The team tackled the matrix multiplication problem by turning it into a single-player 3D board game called ‘TensorGame’. The game is immensely challenging as the number of possible algorithms, even for small cases of matrix multiplication, is larger than the number of atoms in the universe. 

The three-dimensional board represents the multiplication problem and each move represents the next step in solving it. The series of moves made in the game, therefore, represents an algorithm. 

To play the game, the researchers trained a new version of AlphaZero, called ‘AlphaTensor’. Instead of learning the best moves to make in Go or chess, the system learned the best steps to make when multiplying matrices. Then, using DeepMind’s favourite reinforcement learning, the system was rewarded for winning the game in as few moves as possible.

The AI system discovered a way to multiply two 4×4 matrices using only 47 multiplications, rather than the 64 it takes if you were to painstakingly multiply each row with each column from its corresponding matrix. That’s also two steps less than the 49 found by Volker Strassen in 1969, whose multiplication method for 4×4 matrices had held the record for the fastest one for more than 50 years. 

What’s ahead?

The find could boost some computation speeds by up to 20% on hardware such as an Nvidia V100 graphics processing unit (GPU) and a Google tensor processing unit (TPU) v2, but there is no guarantee that those gains would also be seen on a smartphone or laptop.

DeepMind now plans to use AlphaTensor to look for other types of algorithms. “While we may be able to push the boundaries a little further with this computational approach,” Grey Ballard, a computer scientist at Wake Forest University in Winston-Salem, North Carolina, said, “I’m excited for theoretical researchers to start analysing the new algorithms they’ve found to find clues for where to search for the next breakthrough.”