12
$\begingroup$

My question is regarding the paper "Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor". In the paper, the authors show an algorithm for multiplying a $n \times n^c$ and a $n^c \times n$ matrix. The authors show a graph of how the exponent in the time complexity depends on $c$. This graph is clearly convex. This would mean that one can upper bound the time complexity by linearly interpolating the exponent between that case of $c = 0.31389$ (where the exponent is 2) and $c=1$ (where the exponent is $\omega$). This would be useful for stating the time complexity of an algorithm I came up with.

However, they do not prove that the graph is convex. Is it convex? If so, any ideas as to how to cite this fact?

https://arxiv.org/abs/1708.05622

$\endgroup$
4
$\begingroup$

Does Lemma 3.6 of https://arxiv.org/abs/2009.10217 answer your original question of convexity of the matrix multiplication constant?

$\endgroup$
1
  • $\begingroup$ It does! That is exactly what I was looking for! $\endgroup$ – user2316602 Feb 27 at 14:48
2
$\begingroup$

I found an answer in the paper "Fast sparse matrix multiplication" as Theorem 2.4. The authors cite "Fast rectangular matrix multiplications and applications", so that's the original source, I guess. It is possible to do it in a black-box fashion, so it works for any fast multiplication algorithms. That, of course, does not prove convexity but it does allow to upper-bound the exponent, as I needed.

https://www.cs.tau.ac.il/~zwick/papers/sparse.pdf

$\endgroup$
3
  • $\begingroup$ Can you clarify in the answer what exactly says the statement that you found in that paper? $\endgroup$ – Emil Jeřábek Feb 25 at 13:41
  • $\begingroup$ I have added a link to make it easier for people to find the statement. It is written better than I can do it, so I think it is best read in the paper :-) $\endgroup$ – user2316602 Feb 25 at 13:44
  • 2
    $\begingroup$ @user2316602 The problem is that links go stale; this is a fine answer right now but might not be next year or two years from now. It's best to make answers self-contained if you're relying on anything with any more net volatility than, say, Wikipedia. $\endgroup$ – Steven Stadnicki Feb 25 at 17:37

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.