pith. sign in

arxiv: 1708.09398 · v1 · pith:6PEZSFJMnew · submitted 2017-08-30 · 💻 cs.DS · cs.CC· cs.SC· math.RT

Designing Strassen's algorithm

classification 💻 cs.DS cs.CCcs.SCmath.RT
keywords algorithmconstructionstrassenonlyshowingalgorithmsalthoughappears
0
0 comments X
read the original 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).

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.