63
$\begingroup$

It is widely conjectured that $\omega$, the optimal exponent for matrix multiplication, is in fact equal to 2. My question is simple:

What reasons do we have for believing that $\omega = 2$?

I'm aware of fast algorithms like Coppersmith-Winograd, but I don't know why these might be considered evidence for $\omega = 2$.

Naively, it seems to me like a classic example where a community just hopes that a result is true purely for aesthetic reasons. I would love to know if that's essentially the case here.

Improve this question
$\endgroup$
8
  • 12
    $\begingroup$ I suspect the answer is largely aesthetics, and the lack of a good reason for it to be larger than 2. There was a paper in FOCS '05 that gave some group theoretic constructions for matrix mult that matched the current known exponents and also gave 2 group theoretic conjectures which imply $\omega=2$. PDF $\endgroup$
    – Mark Reitblatt
    Commented Mar 8, 2011 at 5:04
  • 5
    $\begingroup$ A few years ago, I had a conversation with Strassen where he said he believed $\omega > 2$. I am not sure what were his reasons, though. $\endgroup$
    – Ryan Williams
    Commented Mar 8, 2011 at 5:20
  • 2
    $\begingroup$ @Ryan, let's hope that Strassen reads cstheory.stackexchange. :) $\endgroup$
    – Steve Flammia
    Commented Mar 8, 2011 at 6:14
  • 3
    $\begingroup$ There is a $\Omega(n\log n)$ lower bound (under some restrictions) due to Ran Raz, so a better conjecture would be that $\omega = 2$ is not achieved (but the infimum is indeed $2$). $\endgroup$
    – Yuval Filmus
    Commented Mar 8, 2011 at 9:51
  • 6
    $\begingroup$ @Yuval, @Steve: 1) $\omega$ is usually defined as a limit. 2) We already know that whatever $\omega$ is, it is not achieved (it is an inf and not a min). See this Coppersmith-Winograd paper: dx.doi.org/10.1137/0211038. From the abstract: "the exponent for matrix multiplication is a limit point, that is, it cannot be realized by any single algorithm." (Given the details of their results, I think this statement cannot quite be taken naively at face value, but this is mostly a technicality.) $\endgroup$
    – Joshua Grochow
    Commented Mar 9, 2011 at 5:49

4 Answers 4

Reset to default
20
$\begingroup$

I'd like to add to Mark Reitblatt's comment and Amir Shpilka's answer. First, one of the conjectures put forward by Cohn, Kleinberg, Szegedy, and Umans is not group-theoretic but is purely combinatorial (Conj. 3.4 in their FOCS '05 paper). This conjecture says that the "strong USP capacity is $\frac{3}{2^{2/3}}$." Coppersmith and Winograd, in exhibiting their currently-best algorithm for matrix multiplication, showed that the USP capacity is this same number $\frac{3}{2^{2/3}}$ (although they did not phrase it quite this way). Although there is a difference between strong USPs and USPs, this is some evidence that their conjecture is at least plausible.

(For their other Conjecture 4.7, which is group-theoretic, I do not know of any similar evidence of plausibility, beyond just intuition.)

Second, I agree with Amir Shpilka that the string of past algorithms has a somewhat ad-hoc feel. However, one of the nice things about the group-theoretic approach is that almost all (not quite all) of the previous algorithms can be phrased in this approach. Although the various group-theoretic constructions in [CKSU] may seem a little ad-hoc on the outside, within the context of the group-theoretic framework they appear significantly more natural and less ad-hoc (at least to me) than many of the previous algorithms.

Improve this answer
$\endgroup$
2
  • $\begingroup$ When I think about Capacity I think about independent sets and cliques. What is the dictionary between USPs and the explicit construction of the underlying graph and is there a structure to these graphs? $\endgroup$
    – Turbo
    Commented Oct 18, 2013 at 2:11
  • 1
    $\begingroup$ Would this answer need an update since 10 years have passed and some no go results have been obtained? $\endgroup$
    – Turbo
    Commented May 10, 2022 at 11:53
28
$\begingroup$

I don't know about others but I can tell you why I tend to believe that $\omega=2$. When you read through the history and development of fast matrix multiplication algorithms, I think that it is hard not to get feeling that all that we need is just a slightly better basic algorithm from which, even using known techniques, $\omega=2$ will follow. Basically, all algorithms today (including group theoretic ones) start with some "simple" construction that is then amplified. Those constructions are clever but they give the reader some sort of an "ad-hoc" feeling. I don't see a reason to believe that we cannot come up with better simple constructions.

Improve this answer
$\endgroup$
0
21
$\begingroup$

There is an analogy I use to justify the conjecture that $\omega = 2$ to myself. I realize this is pretty heuristic, but nevertheless it has served me well, for example, in understanding some of the intuition behind the Cohn et al. paper.

Convolution and matrix multiplication are analogous. If $A$ and $B$ are $n$-by-$n$ matrices and $C = AB$, then $C(i,j) = \sum_{k=1}^n A(i,k) B(k,j)$. If $A$ and $B$ are $n$-length vectors and $C = A*B$, then $C(i) = \sum_{k=1}^n A(k)B(i-k)$. In both cases, the final result is a vector consisting of sums of products, but the relational structure in the input data is different. For convolution, we can use the FFT to compute the answer in $\tilde{O}(n)$ time instead of the trivial $O(n^2)$. Analogously, one might expect an $\tilde{O}(n^2)$ time algorithm for matrix multiplication. The question is: what is the analog of the Fourier transform which can help for matrix multiplication?

Improve this answer
$\endgroup$
-1
$\begingroup$

More likely that it is $O(n^{2} log(n^2))$. Having $\omega = 2$ seems fanciful as constant factor book-keeping doesn't seem like it could scale.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ You misunderstand the definition of $\omega$: it is the infimum of all $c$ such that matrix multiplication can be solved in time $O(n^c)$. If there is a $O(n^2 \log^{10} n)$ matrix multiplication algorithm, this infimum will still be $2$. BTW there is a $\Omega(n^2\log n)$ bound in the model of arithmetic circuits with bounded coefficients. $\endgroup$
    – Sasho Nikolov
    Commented Jan 29, 2017 at 16:51
  • $\begingroup$ @SashoNikolov Thanks for pointing that out. Has anyone tried training a neural net for boolean matmul A*B=C? [A entries, B entries, C entries] -> Bool (correct or incorrect multiply). Curious what circuits the gradient decent/dropouts come up with; if trained circuits have attractors near prime decompositions. On 3x3, 4x4, 5x5, 6x6 it seems an hour of GPU would give some interesting results. $\endgroup$
    – Chad Brewbaker
    Commented Jan 30, 2017 at 17:32

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.