AI Reveals New Possibilities in Matrix Multiplication


Mathematicians love a good puzzle. Even something as abstract as multiplying matrices (two-dimensional tables of numbers) can feel like a game when you try to find the most efficient way to do it. It’s a little like trying to solve a Rubik’s Cube in as few moves as possible — challenging, but alluring. Except that for a Rubik’s Cube, the number of possible moves at each step is 18; for matrix multiplication, even in relatively simple cases, every step can present more than 1012 options.

Over the past 50 years, researchers have approached this problem in many ways, all based on computer searches aided by human intuition. Last month, a team at the artificial intelligence company DeepMind showed how to tackle the problem from a new direction, reporting in a paper in Nature that they’d successfully trained a neural network to discover new fast algorithms for matrix multiplication. It was as if the AI had found an unknown strategy for solving a monstrously complex Rubik’s Cube.
“It’s a very neat result,” said Josh Alman, a computer scientist at Columbia University. But he and other matrix multiplication specialists also emphasized that such AI assistance will complement rather than replace existing methods — at least in the near term. “It’s like a proof of concept for something that could become a breakthrough,” Alman said. The result will simply help researchers on their quest.

[Read More…]