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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Have you already looked into the book: Tensors: geometry and applications by Landsberg? $\endgroup$
    – Suvrit
    Commented 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$
    – Dustin G. Mixon
    Commented 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
    Commented Sep 11, 2016 at 10:53

2 Answers 2

Reset to default
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.]

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\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$
    – Federico Poloni
    Commented 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$
    – András Bátkai
    Commented Dec 10, 2017 at 14:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .