Designing Strassen's algorithm

Abstract

In 1969, Strassen shocked the world by showing that two n x n matrices could be multiplied in time asymptotically less than $O(n^3)$. While the recursive construction in his algorithm is very clear, the key gain was made by showing that 2 x 2 matrix multiplication could be performed with only 7 multiplications instead of 8. The latter construction was arrived at by a process of elimination and appears to come out of thin air. Here, we give the simplest and most transparent proof of Strassen's algorithm that we are aware of, using only a simple unitary 2-design and a few easy lines of calculation. Moreover, using basic facts from the representation theory of finite groups, we use 2-designs coming from group orbits to generalize our construction to all n (although the resulting algorithms aren't optimal for n at least 3).

arXiv commentThis is a simplified, generalized, and self-contained version of Section 5 of arXiv:1612.01527v2 [cs.CC]

References in corpus (8)

• Powers of Tensors and Fast Matrix Multiplication
• Geometric Complexity Theory and Tensor Rank
• Symmetries of matrix multiplication algorithms. I
• On symmetries of the Strassen algorithm
• On the geometry of border rank algorithms for matrix multiplication and other tensors with symmetry
• Matrix multiplication algorithms from group orbits
• The geometry of rank decompositions of matrix multiplication I: 2x2 matrices
• Strassen's 2x2 matrix multiplication algorithm: A conceptual perspective

Cited by in corpus (1)

• Strassen's 2x2 matrix multiplication algorithm: A conceptual perspective