<p>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 &gt; 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$.</p>

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

CC BY-SA 3.0
2011-11-29T16:37:54.570Z
2011-11-29T16:37:54.570Z
Mahdi Cheraghchi
<p>It is well-known the <a href="http://dx.doi.org/10.1109/SFCS.1981.27" rel="noreferrer">result</a> of Coppersmith and Winograd that $O(n^{\omega})$-time cannot be realized by any single algorithm. But I've <a href="http://qwiki.stanford.edu/index.php/Speedup" rel="noreferrer">read</a> 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.</p>

CC BY-SA 3.0
2011-11-29T17:46:21.233Z
2011-11-29T17:46:21.233Z
didest
<p>A minor comment that's too long to be a comment: </p>

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

<p>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)}$.</p>

CC BY-SA 3.0
2011-11-30T01:48:43.967Z
I imagine that the Coppersmith-Winograd algorithm falls into this category?
David Harris
CC BY-SA 3.0
2011-11-30T02:12:49.793Z
@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
CC BY-SA 3.0
2011-11-29T23:16:27.600Z
2011-11-29T23:16:27.600Z
Robin Kothari
<p>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." </p>

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

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

CC BY-SA 3.0
2011-11-30T01:51:04.680Z
I don't see how human knowledge can be part of a mathematical definition
David Harris
CC BY-SA 3.0
2011-11-30T16:22:14.767Z
Recent experience shows that it is much easier to quantify over all algorithms than over all algorithms currently known by humankind ;-)
Markus Bläser
CC BY-SA 3.0
2011-11-29T22:57:59.407Z
2011-11-29T22:57:59.407Z
Bruno
<p>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$.</p>

<p>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 &gt; 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})$.</p>

<p>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?</p>

CC BY-SA 3.0
2011-11-30T16:19:07.037Z
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
CC BY-SA 3.0
2014-07-19T20:31:56.877Z
$\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
<ds.algorithms><linear-algebra>
Definition of matrix-multiplication exponent $\omega$
David Harris
# Definition of matrix-multiplication exponent $\omega$

(Asked by: username_0 on 2011-11-29)

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?

**Tags:** ds.algorithms, linear-algebra
> **Comments:**
> **username_1**: 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.  
> **username_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.  

---

## 4 answers

### Answer by username_3 on 2011-11-29. Score: 22

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.


---

### Answer by username_5 on 2011-11-29. Score: 7

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)}$.

> **Comments:**
> **username_0**: I imagine that the Coppersmith-Winograd algorithm falls into this category?  
> **username_5**: @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.  

---

### Answer by username_4 on 2011-11-29. Score: 6

It is well-known the [result](http://dx.doi.org/10.1109/SFCS.1981.27) of Coppersmith and Winograd that $O(n^{\omega})$-time cannot be realized by any single algorithm. But I've [read](http://qwiki.stanford.edu/index.php/Speedup) 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.


---

### Answer by username_6 on 2011-11-29. Score: 3

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.

> **Comments:**
> **username_0**: I don't see how human knowledge can be part of a mathematical definition  
> **username_1**: Recent experience shows that it is much easier to quantify over all algorithms than over all algorithms currently known by humankind ;-)  

---

