<p>One example where commutativity helps is in computing the determinant. <a href="https://dl.acm.org/doi/10.1145/103418.103462" rel="noreferrer">Nisan</a> showed that any non-commutative algebraic formula that computes the <span class="math-container">$n \times n$</span> determinant must have size <span class="math-container">$2^{\Omega(n)}$</span>. On the other hand, the determinant is computable by commutative algebraic formulas of size <span class="math-container">$n^{O(\log n)}$</span>.</p>

CC BY-SA 4.0
2021-07-09T01:38:52.067Z
2021-07-09T01:38:52.067Z
Robert Andrews
<p>With an associative operation I can rewrite a computation tree</p>
<pre><code>        +
       / \
      +   4
     / \
    +   3
   / \
  +   2
 / \
0   1
</code></pre>
<p>to be more efficient in parallel.</p>
<pre><code>     +
   /   \
  +     +
 / \   / \
1   2 3   4
</code></pre>
<p>Are there situations where assuming <em>commutativity</em> offers computation benefits?</p>

CC BY-SA 4.0
2021-07-07T20:22:42.040Z
Isn't commutativity exploited (required?) by MapReduce?  (E.g. https://courses.cs.washington.edu/courses/cse490h/08au/lectures/mapred.pdf) Maybe somebody who knows more can elaborate.
Neal Young
CC BY-SA 4.0
2021-07-07T20:35:41.443Z
I'd expect commutative operations on sparse structures to be often optimizable by commutativity, but I can't find a good example
xavierm02
<algebra><compilers><term-rewriting-systems>
Commutative operation benefits
andi
# Commutative operation benefits

(Asked by: username_0 on 2021-07-06)

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?

**Tags:** algebra, compilers, term-rewriting-systems

> **Comments:**
> **username_1**: Isn't commutativity exploited (required?) by MapReduce?  (E.g. https://courses.cs.washington.edu/courses/cse490h/08au/lectures/mapred.pdf) Maybe somebody who knows more can elaborate.  
> **username_2**: I'd expect commutative operations on sparse structures to be often optimizable by commutativity, but I can't find a good example  

---

## 1 answers

### Answer by username_3 on 2021-07-09. Score: 6

One example where commutativity helps is in computing the determinant. [Nisan](https://dl.acm.org/doi/10.1145/103418.103462) 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)}$.


---

