0
$\begingroup$

Multiplying two matrices $A \cdot B$ of size $n \times n$ in the trivial way requires $n^3$ computations. However, more efficient algorithms such as the Strassen algorithm have a lower complexity of approximately $\mathcal{O}(n^{2.8})$. There's even the Coppersmith-Winograd algorithm of theoretical complexity $\mathcal{O}(n^{2.37})$.

It seems unlikely that there would be for example a linear function that computes the matrix product, but is there a theoretical limit as to how effective any algorithm to multiply matrices must be, would for example $\mathcal{O}(n^2)$ be possible?

I'm also interested in extending the question beyound matrix multiplication. Are there such "theoretical lower bounds on complexity" for accomplishing a certain task with numerical methods (like multiplying two matrices) in general?

$\endgroup$
  • 1
    $\begingroup$ The obvious lower bound is how many things must be read off in order to make the computation. The matrix product is a function of the $2n^2$ entries, and no entry can safely be omitted from the computation in general, so $\mathcal O(n^2)$ is a lower bound for matrix multiplication. $\endgroup$ – Dustan Levenstein Mar 17 '14 at 13:49
  • $\begingroup$ Or perhaps to be more formal, matrix multiplication has a complexity of $\Omega(n^{2})$. :-) $\endgroup$ – ml0105 Mar 17 '14 at 13:53
  • $\begingroup$ @Dustan Ok, that's a good point. But can we say anything about whether it's possible to create an algorithm that actually has that complexity? $\endgroup$ – naslundx Mar 17 '14 at 14:00
  • $\begingroup$ In general that's a very difficult problem. $\endgroup$ – Dustan Levenstein Mar 17 '14 at 14:02
  • 1
    $\begingroup$ In fact, I think even an optimal algorithm for vanilla multiplication of integers is unknown. (I wrote floating point numbers initially, but that's not what the lecture I remember seeing claimed.) $\endgroup$ – Dustan Levenstein Mar 17 '14 at 14:02
0
$\begingroup$

There is a survey paper by Virginia Vassilevska Williams who showed the currently best bound of $\omega \leq 2.373$.

In the introduction she says:

The best known lower bounds for the problem are of the form $c \cdot n^2$ for explicit constants $c \leq 3$. Perhaps because of this, a majority of experts believe that there should exist an essentially quadratic time algorithm for matrix multiplication. Some prominent experts, however, such as Strassen, have also expressed the opinion that matrix multiplication requires strictly more than quadratic time. The answer has evaded computer science researchers for more than 40 years!

Thus it seems that we don't know more than $2 \leq \omega \leq 2.373$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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