One week after DeepMind revealed an algorithm for multiplying numbers more efficiently, researchers have an even better way to carry out the task.
Multiplying numbers is a common computational problem
A pair of researchers have found a more efficient way to multiply grids of numbers, beating a record set just a week ago by the artificial intelligence firm DeepMind.
The company revealed on 5 October that its AI software had beaten a record that had stood for more than 50 years for the matrix multiplication problem – a common operation in all sorts of software where grids of numbers are multiplied by each other. DeepMind’s paper revealed a new method for multiplying two five-by-five matrices in just 96 multiplications, two fewer than the previous record.
Jakob Moosbauer and Manuel Kauers at Johannes Kepler University Linz in Austria were already working on a new approach to the problem prior to that announcement.
Their approach involves running potential multiplication algorithms through a process where multiple steps in the algorithm are tested to see if they can be combined.
“What we do is, we take an existing algorithm and apply a sequence of transformations that at some point can lead to an improvement. Our technique works for any known algorithm, and if we are lucky, then [the results] need one multiplication less than before,” says Moosbauer.
After DeepMind published its breakthrough, Moosbauer and Kauers used their approach to improve on DeepMind’s method, slicing off another step to set a new record of 95 multiplications. They have published the proof in a pre-print paper, but haven’t yet released details of the approach they used to find improvements on previous methods.
“We wanted to publish now to be the first one out there, because if we can find it in such a short amount of time, there’s quite some risk that we get outdone by someone else again,” says Moosbauer.
The latest paper is entirely focused on five-by-five matrix multiplication, but the method is expected to bring results for other sizes. The researchers say that they will publish details of their technique soon.
Moosbauer says that DeepMind’s approach brought fresh impetus to an area of mathematics that hadn’t been receiving much attention. He hopes that other teams are also now working in a similar vein.
Matrix multiplication is a fundamental computing task used in virtually all software to some extent, but particularly 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.
DeepMind claimed to have seen a boost in computation speed of between 10 and 20 per cent on certain hardware such as an Nvidia V100 graphics processing unit and a Google tensor processing unit v2. But it said that there was no guarantee that similar gains would be seen on everyday tasks on common hardware. Moosbauer says he is sceptical about gains in common software, but that for large and specialised research tasks there could be an improvement.
DeepMind declined a request for an interview about the latest paper, but its researcher Alhussein Fawzi said in a statement: “We’ve been overwhelmed by the incredible reaction to the paper. Our hope was that this work would open up the field of algorithmic discovery to new ideas and approaches. It’s fantastic to see others exploring ideas in this space as well as building on our work so quickly.”
For more such insights, log into www.international-maths-challenge.com.
*Credit for article given to Matthew Sparkes*