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?

Improve this question
$\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
    Commented Jul 7, 2021 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
    Commented Jul 7, 2021 at 20:35

1 Answer 1

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

Improve this answer
$\endgroup$

Your Answer

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

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