DeepMind breaks the matrix multiplication record

DeepMind


DeepMind, the Artificial Intelligence division of Google, has discovered a faster way to perform matrix multiplication, a central problem in computing that affects thousands of everyday tasks and whose previous record dated from 50 years ago.

DeepMind keeps looking for new challenges and after humiliating the world champion of Go, playing checkers, chess, poker or striking down human players in the multiplayer mode of the real-time strategy video game. Starcraft II wants to show off its ability in other compute-intensive aspects.

To do this, they have used their AlphaZero board game with the intention of solving a fundamental mathematical program in computer science. The new challenge has been matrix multiplication, a crucial type of computation at the heart of many applications, from displaying images on a screen to simulating complex physics. It is also critical to machine learning itself.

DeepMind and the ABC in computing

Multiplying two matrices usually involves multiplying the rows of one with the columns of the other. The basic technique for solving the problem is taught in high school. “It’s like the ABC of computing”say from DeepMind’s AI for Science team.

But things get complicated when you try to find a faster method. “Nobody knows the best algorithm to solve it. It is one of the biggest open problems in computing., they clarify. This is because there are more ways to multiply two matrices than there are atoms in the universe (10 to the power of 33). “The amount of possible actions is almost infinite”says Thomas Hubert, an engineer at DeepMind.

To improve the calculation, the researchers used a new version of AlphaZero, the game that DeepMind used against humans in Go or against chess grandmasters. To work with arrays, they created a three-dimensional board game, called TensorGame. The board simulates the multiplication problem and each move represents the next step in solving the problem. The series of moves made in the game represents an algorithm and the reward is to win the game in the least number of moves.

The main result is that AlphaTensor discovered a faster way to multiply two four-by-four matrices than a method devised in 1969 by the German mathematician Volker Strassen, which nobody had been able to improve since then. If the basic high school method is 64 steps and the mathematician’s method is 49, AlphaTensor found a way to do it in 47 steps.

A surprising result, they describe from the mathematical community. “Matrix multiplication is used everywhere in engineering and computer science. Anything you want to solve numerically, you usually use arrays», they explain. We will see its practical applications, but they say to speed up this calculation could have a huge impact on thousands of computing tasks daily, reducing costs and saving energy.


#DeepMind #breaks #matrix #multiplication #record

Leave a Reply

Your email address will not be published. Required fields are marked *