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$
  • 1
    $\begingroup$ Have you already looked into the book: Tensors: geometry and applications by Landsberg? $\endgroup$ – Suvrit Sep 9 '16 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 Sep 9 '16 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 '16 at 10:53
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\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 Dec 10 '17 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 Dec 10 '17 at 14:47
2
$\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.]

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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