Tensors in matrix multiplication algorithms Fast matrix multiplication algorithms, be it the Winograd and Coppersmith algorithm or any further improvement of it, extensively use tensors. In fact, the entire construction is based on tensor analysis. My question is WHY TENSORS? How do tensors help? The following links provide details of the algorithms:
http://www.cs.umd.edu/~gasarch/TOPICS/ramsey/matrixmult.pdf
http://issac-symposium.org/2014/tutorials/ISSAC2014_tutorial_handout_LeGall.pdf
Thanks!
 A: Actually, matrix multiplication can be seen as a bilinear map
$$K^{n\times k}\times K^{k\times m}\rightarrow K^{n\times m},$$
where $K$ is the ground field.
Such a bilinear map can be expressed as a tensor of order 3 of format $(nk)\times (km)\times (nm)$ (any bilinear map $K^{\ell_1}\times K^{\ell_2}\rightarrow K^{\ell_3}$ can be represented by a tensor of format $\ell_1\times\ell_2\times\ell_3$).
The number of (non-commutative) multiplications required to compute the bilinear map then corresponds to the rank of this tensor of order 3. This number of multiplications corresponds to the "order" of recursive algorithms to compute this bilinear map. For instance, Strassen's algorithm corresponds to a rank 7 decomposition of the tensor associated to the multiplication of $2\times 2$ matrices, leading to a general algorithm for multiplying $n\times n$ matrices with complexity $O(n^{\log_2(7)})$.
You may be interested in the following classical reference that explains well this relationship: the book "Algebraic Complexity Theory" by Burgisser, Clausen and Shokrollahi.
