8
$\begingroup$

The $(m,n,p)$-matrix multiplication tensor is a representation of the bilinear map $T\colon\mathbb{R}^{m\times n}\times\mathbb{R}^{n\times p}\rightarrow\mathbb{R}^{m\times p}$ given by $T(A,B)=AB$. Any low-rank decomposition of this tensor leads to a faster-than-naive matrix multiplication algorithm (à la the Strassen algorithm). Actually, to get a fast algorithm, it suffices for arbitrarily small perturbations of this tensor to have low rank; the minimum of such ranks is called the border rank.

Where can I find a recent table of the best known upper and lower bounds on the rank and border rank of the $(m,n,p)$-matrix multiplication tensor for moderately small values of $m$, $n$ and $p$?

Slide 24 here is close to what I want, though I would prefer explicit citations and larger $m$, $n$ and $p$.

Here's a related question that focuses on the $(3,3,3)$ case.

$\endgroup$
3
  • 1
    $\begingroup$ Have you already looked into the book: Tensors: geometry and applications by Landsberg? $\endgroup$
    – Suvrit
    Sep 9, 2016 at 15:28
  • 2
    $\begingroup$ @Survit - I've looked online, but the links I found only provide limited views. While I haven't found what I'm looking for, I did find a drawing of a pickle held to someone's head: ams.org/books/gsm/128/gsm128-endmatter.pdf#page=19 $\endgroup$ Sep 9, 2016 at 20:02
  • $\begingroup$ Being completely not a specialist in this field I nevertheless suggest that I know a person who must know the exact answer to your question. His personal page is spring.inm.ras.ru/osel (Ivan Oseledets) and one of his main research topics (together with E.E. Tyrtyshnikov) are so called tensor train approximations which are something closely related to low-rank approximations for tensors. So, probably you could ask the professor. $\endgroup$
    – VorKir
    Sep 11, 2016 at 10:53

2 Answers 2

3
$\begingroup$

There are upper bounds collections in 1 and 2.

The best known lower bounds for (3,3,3) is $R \geq 19$ by Bläser (3), for (2,2,m) is $R \geq 3m + 2$ by Alekseev (4, in Russian), and general lower bounds in 5 and 6

1 C.-E. Drevet, Md. Nazrul Islam, and É. Schost. "Optimization techniques for small matrix multiplication." Theor. Comp. Sci. 412(22) (2011), pp. 2219-2236.

2 A. V. Smirnov. "The bilinear complexity and practical algorithms for matrix multiplication." Comput. Math. and Math. Physics 53(12) (2013), pp. 1781-1795.

3 M. Bläser. "On the complexity of the multiplication of matrices of small formats." J. of Complexity 19(1) (2003), pp. 43-60.

4 V. B. Alekseev "On bilinear complexity of multiplication of $m \times 2$ and $2 \times 2$ matrices" Chebyshevsky Sbornik 16(4) (2015), pp. 11-27 [in Russian]

5 J.M. Landsberg, G. Ottaviani "New Lower Bounds for the Border Rank of Matrix Multiplication" Theory of Computing 11, 2015

6 A. Massarenti, E. Ravioli "On the rank of $n\times n$ matrix multiplication", arXiv:1211.6320v2 [corrected version of a journal paper in Lin. Alg. Appl.]

$\endgroup$
3
$\begingroup$

There is a table at http://cristal.univ-lille.fr/~sedoglav/FMM/ that (try to) gather such bounds

$\endgroup$
2
  • $\begingroup$ It is considered good practice here to disclose it when you link to your own website. Please add it explicitly to your answer. $\endgroup$ Dec 10, 2017 at 14:05
  • 2
    $\begingroup$ It is also good to summarize the content for the case something happens to the link. $\endgroup$ Dec 10, 2017 at 14:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.