More than 50 years after Strassen's groundbreaking discovery that 2x2 matrices can be multiplied with only 7 multiplications in the coefficient domain, the computational cost of matrix multiplication is still a mystery. Not even for 3x3 matrices the smallest number of multiplications required is known (the long-standing record is 23). For slightly larger matrices, bounds on the smallest number of multiplications have been pushed down in recent years by various authors, using various different search techniques.
We have introduced a new search technique based on performing random walks in a graph whose vertices are correct matrix multiplication schemes and where there are edges between two vertices if one scheme can be transformed into the other in a certain way. While most edges in this graph do not change the number of multiplications, there are some edges that lead to a scheme with one multiplication less.
Paths containing several such edges have led us to schemes that need fewer multiplications than the best previously known schemes. We found such paths by extensive search on mach2 and the computing facilities of the Institute for Algebra and the Institute for Symbolic Artificial Intelligence at JKU.
Part of this research attracted the attention of national and international public media.
References