5
$\begingroup$

With an associative operation I can rewrite a computation tree

        +
       / \
      +   4
     / \
    +   3
   / \
  +   2
 / \
0   1

to be more efficient in parallel.

     +
   /   \
  +     +
 / \   / \
1   2 3   4

Are there situations where assuming commutativity offers computation benefits?

$\endgroup$
2
  • $\begingroup$ Isn't commutativity exploited (required?) by MapReduce? (E.g. courses.cs.washington.edu/courses/cse490h/08au/lectures/…) Maybe somebody who knows more can elaborate. $\endgroup$
    – Neal Young
    Jul 7 at 20:22
  • $\begingroup$ I'd expect commutative operations on sparse structures to be often optimizable by commutativity, but I can't find a good example $\endgroup$
    – xavierm02
    Jul 7 at 20:35
6
$\begingroup$

One example where commutativity helps is in computing the determinant. Nisan showed that any non-commutative algebraic formula that computes the $n \times n$ determinant must have size $2^{\Omega(n)}$. On the other hand, the determinant is computable by commutative algebraic formulas of size $n^{O(\log n)}$.

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