Timeline for Computational complexity of computing the trace of a matrix product under some structure

6 events

when toggle format	what		by	license	comment
May 15, 2020 at 14:09	comment	added	Robert Israel		If $r$ is at most $15$ in the instances you're dealing with, the difference between $O(r^2 d)$ and $O(r d)$ may not be of much practical importance: a $O(r^2 d)$ algorithm might outperform a $O(r d)$ algorithm, depending on details of implementation.
May 15, 2020 at 2:12	history	edited	CComp	CC BY-SA 4.0	added 89 characters in body
May 15, 2020 at 2:08	comment	added	CComp		Thanks. For what I've read about Coppersmith-Winograd algorithm (not much to be honest), it seems to be quite impractical. This is something I'll implement as a part of a bigger algorithm. As a reference, I typically have $d \in [200, 1700]$ and $r \in [3, 15]$. Using $r \ll d$ in the question might have been a slight abuse (maybe?). My biggest concern is for question 1, can I go from $r^2d$ to $rd$? Maybe there's a simple way of verifying that's not possible.
May 15, 2020 at 1:01	comment	added	user44191		The answer may depend on how "tall" your matrix is; if $r > O(d^{0.7})$ (not a tight bound), then a naive application of the Coppersmith-Winograd algorithm gets the answer faster than the naive algorithm for part 1; for part 2, the restriction is $r > O(d^{0.4})$ (both if I've done my arithmetic right). en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm
May 15, 2020 at 0:11	review	First posts
May 15, 2020 at 1:01
May 15, 2020 at 0:07	history	asked	CComp	CC BY-SA 4.0