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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ It is interesting that commutative algorithm can give rise to a non-commutative algorithm. $\endgroup$
    – Turbo
    May 20, 2015 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, 2015 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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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