Artificial intelligence discovers optimized algorithms

AlphaZero's record hunt continues. But the artificial intelligence (AI)-based software no longer tries to find the best ways to play chess or Go. Instead, the slightly modified program is now called AlphaTensor and searches for the shortest algorithms for certain computer operations: the multiplication of matrices, which is used for weather forecasts, among other things. AlphaTensor has already discovered more than 70 improved algorithms, reports a group from Google-owned DeepMind in London in the journal Nature.

Algorithms are mathematical calculation methods to solve a problem. According to the researchers, such methods have been used for thousands of years, and they now play a central role in many computer functions such as image processing.

"Improving the efficiency of algorithms for fundamental computations can have far-reaching implications as it can affect the overall speed of a large set of computations," the authors, led by Alhussein Fawzi, write. For example, the matrix multiplication algorithms sought by AlphaTensor are used to process images on smartphones, recognize voice commands, generate graphics for computer games, compress data and videos, and much more.

AlphaTensor should now not only prove the correctness of known algorithms, but also actively search for the shortest possible algorithms - and thus increase the efficiency of the calculations. In fact, the AI ​​independently found many algorithms that are now considered the shortest for multiplying two matrices of a certain size. But beyond that, AlphaTensor discovered computational methods that were better than those previously devised by humans.

A look back: In 1969 the German mathematician Volker Strassen showed that a relatively simple arithmetic operation such as the multiplication of two simple matrices can be carried out in seven calculation steps instead of eight. This caused a stir among mathematicians. Other algorithms also optimized roads at the time.

According to the researchers, although efforts have since been made to achieve further improvements, this had not been achieved - until now: "We are improving Strassen's two-stage algorithm for the first time to our knowledge since its introduction in 1969 for multiplying four by four matrices,” the researchers write.

For example, if you multiply a four-by-five matrix by a five-by-five matrix, the traditional algorithm has 100 computation steps. Mathematicians were able to reduce this number to 80, but only AlphaTensor found an algorithm with only 76 steps. With larger matrices, the potential for improvement is usually much higher, writes the team.

"Building on our research, we hope to advance a larger body of work -- the application of AI to help society solve some of the most pressing challenges in math and science," some of the authors say in a DeepMind release quoted.

Holger Hoos from the Rheinisch-Westfälische Technische Hochschule Aachen (RWTH) sees the work as "undoubtedly interesting" methodologically, but not as groundbreaking. According to the expert, the matrix multiplication approach could be very interesting for algorithmists and mathematicians working in this field. "But I don't see any signs of a breakthrough in the field of automatic algorithm construction."