4
$\begingroup$

Let $f(n)$ denote the minimum number of arithmetic operations needed for multiplying two $n\times n$ matrices, and $\omega = \inf\{p \ge 0: f(n) = O(n^p)\}$ be the matrix multiplication exponent. Is it true that for every $\epsilon > 0$, $f(n) = \Omega(n^{\omega - \epsilon})$?

Equivalently, if we define $\underline{\omega} = \sup\{p \ge 0: f(n) = \Omega(n^p)\}$, is it true that $\omega = \underline{\omega}$?

The above does not seem to be immediately true, since it might be possible that: (1) for infinitely many $n$, $f(n) = \Theta(n^{2.3})$; (2) for infinitely many $n$, $f(n) = \Theta(n^{2.1})$. Assuming these, we have $\omega \ge 2.3$, yet there is no uniform lower bound of, say, $\Omega(n^{2.2})$.

Improve this question
$\endgroup$
1
  • 6
    $\begingroup$ Matrix multiplication has a recursive structure, which is exploited by all known algorithms with an exponent less than 3. (Directly in the early algorithms, and indirectly in later algorithms.) In particular, they find an algorithm for k by k matrix mult for some fixed k, and extrapolate to all n > k. This structure basically guarantees that if you have an O(n^c) operations algorithm for infinitely many n, then you have it for all but finitely many n (thus for all n, hiding the rest in the big-O). In principle you need a."bilinear matrix mult" alg, but this is essentially WLOG $\endgroup$
    – Ryan Williams
    Commented Feb 23 at 22:30

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.