5
$\begingroup$

What is known about commutative algorithms like Winograd algorithm and its variants for Matrix Multiplication? Why is there not much study on them? Can they be asymptotically as efficient as Non-commutative algorithms?

Update

Existence of $O(n^\omega)$ non-commutative algorithms for matrix multiplication implies existence of $O(n^\omega)$ commutative algorithms. Does converse statement hold truth?

$\endgroup$
7
$\begingroup$

In answer to the "Update": yes, for any $c$, the existence of an $O(n^c)$ non-commutative algorithm for matrix multiplication is equivalent to the existence of an $O(n^c)$ commutative algorithm for matrix multiplication (I am assuming, here, that all algorithms are algebraic, in the sense of algebraic circuits). This is because any algebraic circuit computing a bilinear map can be converted into a bilinear circuit at the expense of at most a factor of 2 in the size.

$\endgroup$
  • $\begingroup$ It is interesting that commutative algorithm can give rise to a non-commutative algorithm. $\endgroup$ – T.... May 20 '15 at 17:25
  • $\begingroup$ It is interesting, but it is a simple consequence of the fact that the algorithms are bilinear. $\endgroup$ – Greg Kuperberg May 20 '15 at 18:34
5
$\begingroup$

Commutative algorithms are not studied that much, because you cannot use them recursively by cutting larger matrices into smaller blocks like you do in Strassen's algorithm.

Since every noncommutative algorithm is a commutative one, commutative algorithms can be trivially as efficient as noncommutative ones.

$\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.