Matrix multiplication is a well studied problem which is recently back in the news due to deepmind.

That got me wondering has anyone looked at the more general problem of faster tensor multiplication? I'm avoiding all that stuff about tensor transformations so from here on out a tensor is just a n-dimensional array of numbers and nothing more.

Given a sequence of tensors $t_0, t_1 .. t_{r-1}$ of dimensions $n_0, n_1, ... n_{r-1}$ and to each tensor a list of strings called its indices $t_0$ has a list of size $n_0$ and $t_1$ has a list of size $n_1$, etc... we then define the tensor product $t_0 ... t_{r-1}$ as the new tensor summed over repeated indices.

At this level generality it might be overtly optimistic to expect too many algorithms beyond the trivial one but even something as focused as $\sum_{i,j} a_{ijk} b_{lij} = c_{kl}$ i don't know any non trivial algorithms for.

  • 3
    $\begingroup$ $\sum_{i,j}a_{i,j,k}b_{l,i,j}$ is plain matrix multiplication, where pairs $(i,j)$ serve as indices. $\endgroup$ Oct 18, 2022 at 6:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.