An artificial intelligence created by the firm DeepMind has discovered a new way to multiply numbers, the first such advance in over 50 years. The find could boost some computation speeds by up to 20 per cent, as a range of software relies on carrying out the task at great scale.
Matrix multiplication 鈥� where two grids of numbers are multiplied together 鈥� is a fundamental computing task used in virtually all software to some extent, but particularly so in graphics, AI and scientific simulations. Even a small improvement in the efficiency of these algorithms could bring large performance gains, or significant energy savings.
For centuries, it was believed that the most efficient way of multiplying matrices would be proportional to the number of elements being multiplied, meaning that the task becomes proportionally harder for larger and larger matrices.
Advertisement
But the mathematician Volker Strassen proved in 1969 that multiplying a matrix of two rows of two numbers with another of the same size doesn鈥檛 necessarily involve eight multiplications and that, with a clever trick, it can be reduced to seven. This approach, called the , requires some extra addition, but this is acceptable because additions in a computer take far less time than multiplications.
The algorithm has stood as the most efficient approach on most matrix sizes for more than 50 years, although some slight improvements that aren鈥檛 easily adapted to computer code have been found. But DeepMind鈥檚 AI has now discovered a faster technique that works perfectly on current hardware. The company鈥檚 new AI, AlphaTensor, started with no knowledge of any solutions and was presented with the problem of creating a working algorithm that completed the task with the minimum number of steps.
It found an algorithm for multiplying two matrices of four rows of four numbers using just 47 multiplications, which outperforms Strassen鈥檚 49 multiplications. It also developed improved techniques for multiplying matrices of other sizes, 70 in total.
AlphaTensor discovered thousands of functional algorithms for each size of matrix, including 14,000 for 4脳4 matrices alone. But only a small minority were better than the state of the art. The research builds on AlphaZero, DeepMind鈥檚 game-playing model, and has been two years in the making.
at DeepMind says the results are mathematically sound, but are far from intuitive for humans. 鈥淲e don鈥檛 really know why the system came up with this, essentially,鈥� he says. 鈥淲hy is it the best way of multiplying matrices? It鈥檚 unclear.鈥�
鈥淪omehow, the neural networks get an intuition of what looks good and what looks bad. I honestly can鈥檛 tell you exactly how that works. I think there is some theoretical work to be done there on how exactly deep learning manages to do these kinds of things,鈥� says Fawzi.
DeepMind found that the algorithms could boost computation speed by between 10 and 20 per cent on certain 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 common devices like a smartphone or laptop.
at the University of Sussex, UK, says that a range of software run on supercomputers and powerful hardware, like AI research and weather simulation, is effectively large-scale matrix multiplication.鈥淚f this type of approach was actually implemented there, then it could be a sort of universal speed-up,鈥� he says. 鈥淚f Nvidia implemented this in their CUDA library [a tool that allows GPUs to work together], it would knock some percentage off most deep-learning workloads, I鈥檇 say.鈥�
at Birkbeck, University of London, says the new algorithms could boost the efficiency of a wide range of software, because matrix multiplication is such a common problem 鈥� and more algorithms are likely to follow.
鈥淚 believe we鈥檒l be seeing AI-generated results for other problems of a similar nature, albeit rarely something as central as matrix multiplication. There鈥檚 significant motivation for such technology, since fewer operations in an algorithm doesn鈥檛 just mean faster results, it also means less energy spent,鈥� he says. If a task can be completed slightly more efficiently, then it can be run on less powerful, less power-intensive hardware, or on the same hardware in less time, using less energy.
But DeepMind鈥檚 advances don鈥檛 necessarily mean human coders are out of a job. 鈥淪hould programmers be worried? Maybe in the far future. Automatic optimisation has been done for decades in the microchip design industry and this is just another important tool in the coder鈥檚 arsenal,鈥� says Lachish.
Nature
