| In the summer of 1925, the young physicist Werner Heisenberg traveled to the remote island of Helgoland seeking relief from a bad bout of seasonal allergies. He returned 10 days later with an equation that's now central to the theory of quantum physics. While the equation correctly predicted the results of experiments, there was just one problem: It involved bizarre rules for manipulating tables of numbers. Heisenberg himself didn't know what to think about the math until his mentor, Max Born, recognized those tables as then-obscure mathematical objects called matrices.
A hundred years later, matrices are anything but obscure. They have countless applications in science and technology, from fundamental physics to computer graphics to artificial intelligence. And the search for better matrix multiplication algorithms ranks among the most iconic problems in computer science.
Matrices come from a branch of mathematics called linear algebra, which studies simple equations involving multiple variables. The central mathematical objects in linear algebra, called vectors, are lists of numbers that describe a specific property of a system: the spatial orientation of an object, the state of a quantum particle, or even the meaning of a word. Matrices, which are two-dimensional tables of numbers, represent processes that transform one vector into another. In the simplest case, a matrix might represent a specific way to rotate an object. But matrices can also represent more exotic transformations. In physics, they describe how quantum states evolve over time. And in computer science, they control how AI models like ChatGPT generate their outputs when given an input.
If there are two consecutive transformations, you need to multiply the corresponding matrices, which involves adding and multiplying their entries in specific combinations. But this standard approach becomes painfully slow when applied to large matrices, like the ones used in AI models. Researchers aim to devise better matrix multiplication algorithms — procedures that get the same answer as the standard method using a more efficient sequence of steps. For over 50 years, the quest for better algorithms has been a rich vein of study.
What's New and Noteworthy
The study of matrix multiplication algorithms began in 1969, when the mathematician Volker Strassen discovered a way to compute the product of 2-by-2 matrices by multiplying specific combinations of their entries only seven times, compared to eight for the standard procedure. That may not sound like a lot, but one fewer multiplication step adds up when you repeatedly chop a large matrix into smaller blocks and apply Strassen's algorithm each time. Strassen's discovery kicked off a decades-long search for the best possible algorithm for multiplying very large matrices. In 2021, Kevin Hartnett surveyed the history of matrix multiplication algorithms and the latest developments. And last year, Steve Nadis reported on a new method that yielded the biggest improvement in more than a decade.
Some researchers take a different approach to the search for matrix multiplication algorithms. Instead of trying to find the best algorithm for large matrices, they seek better methods that work at smaller scales, such as 4-by-4 or 5-by-5 matrices. In 2022, researchers at Google DeepMind notably contributed to this effort using a qualitatively new approach: They trained an AI system called AlphaTensor to automate the search for matrix multiplication algorithms, and it discovered ones that worked better in a few special cases. I covered that result in my first story as a computer science reporter. Quanta also produced a video exploring how AlphaTensor's search works.
Ultimately, researchers study matrix multiplication because it's a well-established way to solve problems in linear algebra. But it's not the only way. In 2021, Hartnett reported that in some cases an alternative approach that harnesses the power of randomness is slightly faster than the best known matrix multiplication algorithm. It may be a small improvement, but it illustrates that the study of matrix multiplication algorithms remains full of surprises. As the computer scientist Renfei Zhou put it in an interview with Nadis, "People are still in the very early stages of understanding this age-old problem." | 
