Among higher mathematical concepts, matrix multiplication is one of the most pervasive operations one can find. It’s also one of the least understood.
In an upcoming working group, SFI Omidyar Fellow Josh Grochow and colleagues will try to improve on what mathematicians and computer scientists already know about the subject and, in the process, move toward a deeper understanding of complexity science itself.
Though the name “matrix multiplication” may not be familiar, the idea and its applications likely are. In simplest form, matrices are ways of representing systems of equations as rectangular arrays of variables.
Matrix multiplication refers to methods of manipulating such arrayed systems of equations by taking the solutions of one equation system and using them as the inputs for another system. It turns out that “multiplying” matrices is computationally equivalent to solving such equation systems manually – but offers additional mathematical structure that aids in understanding their complexities.
Biologists use matrix multiplication to study species’ population dynamics; economists use it to predict market behavior; and graphics processing systems use it to play videos, edit photographs, and generate 3D simulations in a variety of applications.
Computationally speaking, matrix multiplication turns out to be a flagship question in complexity theory, Grochow says, in part because of its ubiquity and the surprise 1969 discovery of a way to beat the brute-force approach solving equation systems variable-by-variable and equation-by-equation.
“Once people realized they could multiply matrices faster than the naive algorithm,” he says, “it opened up new horizons for computer scientists and engineers.”
In spite of both practical and theoretical progress, however, deeper truths about why the algorithms researchers were discovering worked remained a mystery. Beginning in 2003, Henry Cohn and Christopher Umans proposed using a field of mathematics called group theory to link many of the algorithms together, an idea they realized with help from Robert Kleinberg (Cornell) and Balasz Szegedy (University of Toronto).
“What we’ve been trying to do now is take that framework and push it further,” Grochow says. “Can we use it to get some explanatory power?” If so, it could lead to better algorithms for matrix multiplication, though “the real goal is a better understanding of computational complexity” and complexity science, he says. Cohn (Microsoft Research and MIT), Umans (Caltech), and mathematician Jonah Blasiak (Drexel University) will join Grochow for the working group. Mathematician Thomas Church (Stanford), who has worked with the group before, will join in future discussions.