Colloquially, the definition of the matrix-multiplication exponent $\omega$ is the smallest value for which there is a known $n^{\omega}$ matrix-multiplication algorithm. This is not acceptable as a formal mathematical definition, so I guess the technical definition is something like the infimum over all $t$ such that there exists a matrix-multiplication algorithm in $n^t$.

In this case, we cannot say there is an algorithm for matrix-multiplication in $n^{\omega}$ or even $n^{\omega + o(1)}$, merely that for all $\epsilon > 0$ there exists an algorithm in $n^{\omega + \epsilon}$. Often, however, papers and results which use matrix-multiplication will report their cost as simply $O(n^{\omega})$.

Is there some alternate definition of $\omega$ that permits this usage? Are there any results that guarantee that an algorithm of time $n^{\omega}$ or $n^{\omega + o(1)}$ must exist? Or is the usage $O(n^{\omega})$ simply sloppy?

  • 2
    If you just want to use the matrix multiplication as a black-box, the easiest way is to say "Let $\omega$ be such that we can multiply $n \times n$-matrices with $O(n^\omega)$ arithmetic operations". Of course, $\omega$ is not the exponent of matrix multiplication then, but can be arbitrarily close. If you want to state the exponent of your final running in decimal representation, currently you have to round anyway, since all nontrivial estimates for $\omega$ that I am aware of are either irrational numbers or infinite sequences. – Markus Bläser Nov 30 '11 at 16:19
  • 2
    $\omega$ is typically defined as the infimum over all reals $k$ for $n$ going to $\infty$ such that there is an $O(n^k)$ time algorithm that multiplies two $n\times n$ matrices (where the time is the number of additions, multiplications and divisions in the underlying field). This also means that technically we should always write $n^{\omega+o(1)}$ but that gets messy, so when you see $O(n^\omega)$ you should think $O(M(n))$ where $M(n)$ is the runtime of a matrix multiplication algorithm. – virgi Jul 19 '14 at 20:31

The matrix multiplication exponent being $\omega$ does not guarantee that there is an algorithm that runs in time $O(n^\omega)$, but only that for each $\epsilon > 0$, there is an algorithm that runs in $O(n^{\omega+\epsilon})$. Indeed if you can find an algorithm that runs in time $O(n^2 \mathrm{polylog}(n))$, then this shows that $\omega = 2$.

You can find the formal definition in the book Algebraic Complexity Theory by Peter Bürgisser, Michael Clausen, Amin Shokrollahi.

A minor comment that's too long to be a comment:

Sometimes when you have a problem for which there is an algorithm with running time $O(n^{k+\epsilon})$ for every $\epsilon>0$, there is an algorithm with running time $n^{k+o(1)}$.

For example, sometimes you get algorithms that go like $f(1/\epsilon)n^{k+\epsilon}$ for some fast growing function $f$ (like $2^{2^{1/\epsilon}}$). If you set $f(1/\epsilon)$ to (say) $\log n$, then $\epsilon$ will be o(1). In the example with $f(1/\epsilon)$ being $2^{2^{1/\epsilon}}$, you can choose $1/\epsilon$ to be $\log \log \log n$, which gives $\epsilon = 1/ (\log \log \log n)$, which is o(1). So the final running time of this algorithm will be $n^{k+o(1)}$, since $\log n$ is also $n^{o(1)}$.

  • I imagine that the Coppersmith-Winograd algorithm falls into this category? – David Harris Nov 30 '11 at 1:48
  • 2
    @DavidHarris: Don't know about that. Maybe someone who understands the algorithm might be able to shed some light on that. I just meant to say that often $O(n^{k+\epsilon})$ isn't as bad as it looks. – Robin Kothari Nov 30 '11 at 2:12

It is well-known the result of Coppersmith and Winograd that $O(n^{\omega})$-time cannot be realized by any single algorithm. But I've read that they restricted to algorithms based on Strassen-like bilinear identities, so I don't know for sure since the paper is behind a paywall.

I do not agree with your statement in the question that $\omega$ is not well-defined by "the smallest value for which there is a known $n^ω$ matrix-multiplication algorithm." When people are using this constant, it is because their algorithm relies on a matrix multiplication, and by a complexity $n^\omega$, they mean "the optimal complexity of our algorithm is given by the optimal algorithm for matrix multiplication."

I am not saying that it is not possible to define $\omega$ otherwise (e.g. saying that $\omega$ is the best achievable complexity).

Btw, the best known upper bound for matrix multiplication has just been improved to $2.3737$ if I am not mistaken.

  • 3
    I don't see how human knowledge can be part of a mathematical definition – David Harris Nov 30 '11 at 1:51
  • 2
    Recent experience shows that it is much easier to quantify over all algorithms than over all algorithms currently known by humankind ;-) – Markus Bläser Nov 30 '11 at 16:22

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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