4
$\begingroup$

The recent publication in Nature of "Discovering faster matrix multiplication algorithms with reinforcement learning" by Fawzi et al. has shown a method for discovering fewer element multiplication steps in multiplying two matrices. The method is, to over simplify considerably, statistical, yet the resulting multiplication/addition schemas are combinatorial - i.e. the method may well be magic/oracular but the result is easily checkable.

From figure 3 in the paper, it gives minimum previously known mults for 2x2, 3x3, 4x4, and 5x5 matrices, 7,23,49, and 98 respectively, and the better ones found by their method for 4 and 5, namely 47 and 96 (for binary matrices).

It would be nice to know if there has been any research into determining if there are any exact lower bounds for these constants.

Is it known that 7 is the minimum for 2x2? That seems likely given the amount of investigation into it, but I don't think I've heard of any proof that that is the minimum. Maybe with an astronomical number of additions, one can get 6 mults or on the other hand there could be a proof that beyond some number of additions there is nothing more that can be done.

How about 23 mults for 3x3? There could easily be fewer mults but it is beyond our current search capabilities and maybe new techniques like RL/AlphaZero could be developed to hand it to us for checking.

A cursory search of OEIS doesn't turn up anything likely for 1,7,23. But of course, after 1, those values are in question.

Like Ramsey numbers, it may be hard to get exact lower bounds even for small constants. I'm just wondering what is known.

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ According to "On multiplication of 2 × 2 matrices" by Winograd, 7 multiplications is indeed optimal for a 2x2 matrix. $\endgroup$
    – Jake
    Commented Oct 7, 2022 at 18:26
  • 1
    $\begingroup$ @Mitch yes [added because comment needs 15 characters] $\endgroup$
    – Chao Xu
    Commented Oct 8, 2022 at 17:43
  • 1
    $\begingroup$ I am far from an expert, but the best lower bound I am aware of is 19 and can be found in On the complexity of the multiplication of matrices of small formats, Markus Bläser. Found it thanks to this paper arxiv.org/abs/1903.11391 which can also be interesting for you. $\endgroup$
    – holf
    Commented Oct 9, 2022 at 5:27
  • 1
    $\begingroup$ Even the border rank of 2x2 matrix multiplication is known to be 7: arxiv.org/abs/math/0407224. This means that there is no sequence of tensors of rank 6 whose limit is <2,2,2>, the 2x2 matrix multiplication tensor. For a further generalization, see cjtcs.cs.uchicago.edu/articles/2018/5/cj18-05.pdf. $\endgroup$
    – Yuval Filmus
    Commented Oct 10, 2022 at 6:13
  • 1
    $\begingroup$ There are also lower bounds for all values of $n$, for example theoryofcomputing.org/articles/v011a011/v011a011.pdf. $\endgroup$
    – Yuval Filmus
    Commented Oct 10, 2022 at 6:14

0

Reset to default

Your Answer

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