<p>Okay, I've given it a bit of thought and I see that the algorithm is very easy.</p>

<p>Example: Let % denote "commutes". Let A % B, A % C, B % C, B % X.</p>

<p>Compute ABAAXCBA:</p>

<p>Let us keep a "result", an "active multiset" and a "remaining suffix". Let us append a special "$" symbol that commutes with noone onto the string.</p>

<p><strong>Invariant</strong>: the product of "result", active multiset and the remaining suffix equals the product of original string.</p>

<p><strong>Invariant</strong>: all items in the active multiset commute.</p>

<p>At each new element of the suffix, drop elements from the active multiset that don't commute with it into the product, and insert the element into the multiset.</p>

<pre><code>(1, {}, ABAAXCBA$) -&gt;
(1, {A:1}, BAAXCBA$) -&gt; 
(1, {A:1, B:1}, AAXCBA$) -&gt;
(1, {A:2, B:1}, AXCBA$) -&gt;
(1, {A:3, B:1}, XCBA$) -&gt; (drop A^3)
(A^3, {B:1, X:1}, CBA$) -&gt;
(A^3 X, {B:1, C:1}, BA$) -&gt;
(A^3 X, {B:2, C:1}, A$) -&gt;
(A^3 X, {B:2, C:1, A:1}, $) -&gt;
(A^3 X B^2 C A, {$}, )
</code></pre>

<p>This version has at most O(|A|) (size of alphabet) overhead per input symbol and it does an optimal number of multiplications.</p>

CC BY-SA 2.5
2010-09-10T05:28:36.177Z
To the downvoter: care to elaborate about the reason?
jkff
CC BY-SA 2.5
2010-09-11T14:48:41.400Z
If I understand the algorithm, it is not optimal. For `AABB`, where A & B freely commute, your algorithm appears to require three multiplications, where only two are required (`let x=AB in xx`). I'm guessing the downvoter didn't like you presenting an answer without any attempt to justify its optimality.
Charles Stewart
CC BY-SA 2.5
2010-09-12T23:26:04.250Z
I'm the downvoter.  Why should we believe your algorithm computes optimal results?  In particular, how does it optimize the number of multiplications needed to compute AAAAAAAAAAAAAAAAAAAAAAAAAAA?  (On the other hand, you haven't told us exactly what "optimal" means.)
Jeffε
CC BY-SA 2.5
2010-09-13T17:41:40.457Z
Okay, you're right.
jkff
CC BY-SA 2.5
2010-09-09T08:26:15.133Z
2010-09-09T11:00:48.497Z
2010-09-09T11:00:48.497Z
jkff
<p>Let us say I have a semigroup M and its basis B. I know which elements of B commute.</p>

<p>What is the most efficient way to do multiplication in such a semigroup?</p>

<p>Essentially, this is a question of how to reduce "ABAAAXBCAAB" to "AAAABXAABBC" knowing that A, B and C commute with each other but not with X (after such a transform I can, for example, compute AAAA as (A^2)^2, or even store pre-computed powers of each element of B).</p>

CC BY-SA 2.5
2010-09-09T08:09:07.530Z
What is your cost model?  Is "AABC" meant to be more efficient that "CAAB"?
Charles Stewart
CC BY-SA 2.5
2010-09-09T08:16:29.420Z
My cost model is that I want to minimize the number of multiplications, but the multiplications themselves are equivalent in cost.
jkff
CC BY-SA 2.5
2010-09-09T08:18:58.333Z
I guess a reasonable simplification is that any consecutive sequence of letters "costs" as much as a pair, so the goal is to get like symbols close together
Suresh Venkat
CC BY-SA 2.5
2010-09-09T08:28:34.443Z
Yes of course, that's the point. See my own answer.
jkff
CC BY-SA 2.5
2010-09-09T08:53:32.087Z
Some people might not be able to remember what a semigroup is. It is basically just an associative binary relation: http://en.wikipedia.org/wiki/Semigroup
Emil
CC BY-SA 2.5
2010-09-09T09:34:40.670Z
I think you meant "an associative binary operation".
jkff
CC BY-SA 2.5
2010-09-09T11:37:56.833Z
If the semigroup is generated by a single element A, the problem of finding the most efficient way to compute A^n is equivalent to finding a minimum-length addition chain ending with n, which is discussed in http://cstheory.stackexchange.com/questions/912/is-it-hard-to-find-optimal-addition-chains.  My understanding from that question is that even in this case, we do not know how to find the optimal way in time polynomial in n, although this is computable exactly in time 2^{O(log n log log n)} and (1+o(1))-approximable in time polylogarithmic in n.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-09T11:49:13.960Z
You're right; however, I think I'll be quite satisfied with the standard binary exponentiation.
jkff
CC BY-SA 2.5
2010-09-09T11:58:37.837Z
I suspect that rearranging a product so that the same generators become adjacent as much as possible does not necessarily minimizes the number of multiplications required to compute the product.  Here is what might be a counterexample.  Consider the semigroup generated by A, B and C where the only relation is that A and B commute.  Suppose that we want to compute P=AB⋅C⋅(AB)^2⋅C⋅(AB)^4⋅C⋅…⋅C⋅(AB)^{2^k}.  (more)
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-09T11:59:09.570Z
(cont’d)  By first computing M=AB, we can compute P by 3k+O(1) multiplications.  However, if we arrange the product to A⋅B⋅C⋅A^2⋅B^2⋅C⋅A^4⋅B^4⋅C⋅…⋅C⋅A^{2^k}⋅B^{2^k}, a naive method would require 4k+O(1) multiplications and it seems difficult to reduce it to 3k+O(1).
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-09T13:00:18.863Z
You're right again. However, if I'm given just a string, then I don't think I can get asymptotically much better than the arrangement in my answer, because detecting such periodicity might be computationally difficult.
jkff
CC BY-SA 2.5
2010-09-09T14:01:51.973Z
If you are satisfied with your solution, I have no complaint about it.  However, if you are looking for something more, I suggest you to revise the question so that it is clear that you are not only interested in finding the _most efficient_ way to compute a product but _somewhat efficient_ ways, stating the exact meaning of this _somewhat efficient_ you are interested in.
Tsuyoshi Ito
<co.combinatorics><algebra>
Optimizing multiplication in a partly commutative semigroup
jkff
# Optimizing multiplication in a partly commutative semigroup

(Asked by: username_0 on 2010-09-09)

Let us say I have a semigroup M and its basis B. I know which elements of B commute.

What is the most efficient way to do multiplication in such a semigroup?

Essentially, this is a question of how to reduce "ABAAAXBCAAB" to "AAAABXAABBC" knowing that A, B and C commute with each other but not with X (after such a transform I can, for example, compute AAAA as (A^2)^2, or even store pre-computed powers of each element of B).

**Tags:** co.combinatorics, algebra
> **Comments:**
> **username_1**: What is your cost model?  Is "AABC" meant to be more efficient that "CAAB"?  
> **username_0**: My cost model is that I want to minimize the number of multiplications, but the multiplications themselves are equivalent in cost.  
> **username_2**: I guess a reasonable simplification is that any consecutive sequence of letters "costs" as much as a pair, so the goal is to get like symbols close together  
> **username_0**: Yes of course, that's the point. See my own answer.  
> **username_3**: Some people might not be able to remember what a semigroup is. It is basically just an associative binary relation: http://en.wikipedia.org/wiki/Semigroup  
> **username_0**: I think you meant "an associative binary operation".  
> **username_4**: If the semigroup is generated by a single element A, the problem of finding the most efficient way to compute A^n is equivalent to finding a minimum-length addition chain ending with n, which is discussed in http://cstheory.stackexchange.com/questions/912/is-it-hard-to-find-optimal-addition-chains.  My understanding from that question is that even in this case, we do not know how to find the optimal way in time polynomial in n, although this is computable exactly in time 2^{O(log n log log n)} and (1+o(1))-approximable in time polylogarithmic in n.  
> **username_0**: You're right; however, I think I'll be quite satisfied with the standard binary exponentiation.  
> **username_4**: I suspect that rearranging a product so that the same generators become adjacent as much as possible does not necessarily minimizes the number of multiplications required to compute the product.  Here is what might be a counterexample.  Consider the semigroup generated by A, B and C where the only relation is that A and B commute.  Suppose that we want to compute P=AB⋅C⋅(AB)^2⋅C⋅(AB)^4⋅C⋅…⋅C⋅(AB)^{2^k}.  (more)  
> **username_4**: (cont’d)  By first computing M=AB, we can compute P by 3k+O(1) multiplications.  However, if we arrange the product to A⋅B⋅C⋅A^2⋅B^2⋅C⋅A^4⋅B^4⋅C⋅…⋅C⋅A^{2^k}⋅B^{2^k}, a naive method would require 4k+O(1) multiplications and it seems difficult to reduce it to 3k+O(1).  
> **username_0**: You're right again. However, if I'm given just a string, then I don't think I can get asymptotically much better than the arrangement in my answer, because detecting such periodicity might be computationally difficult.  
> **username_4**: If you are satisfied with your solution, I have no complaint about it.  However, if you are looking for something more, I suggest you to revise the question so that it is clear that you are not only interested in finding the _most efficient_ way to compute a product but _somewhat efficient_ ways, stating the exact meaning of this _somewhat efficient_ you are interested in.  

---

## 1 answers

### Answer by username_0 on 2010-09-09. Score: -1

Okay, I've given it a bit of thought and I see that the algorithm is very easy.
Example: Let % denote "commutes". Let A % B, A % C, B % C, B % X.
Compute ABAAXCBA:
Let us keep a "result", an "active multiset" and a "remaining suffix". Let us append a special "$" symbol that commutes with noone onto the string.
Invariant: the product of "result", active multiset and the remaining suffix equals the product of original string.
Invariant: all items in the active multiset commute.
At each new element of the suffix, drop elements from the active multiset that don't commute with it into the product, and insert the element into the multiset.
(1, {}, ABAAXCBA$) ->
(1, {A:1}, BAAXCBA$) -> 
(1, {A:1, B:1}, AAXCBA$) ->
(1, {A:2, B:1}, AXCBA$) ->
(1, {A:3, B:1}, XCBA$) -> (drop A^3)
(A^3, {B:1, X:1}, CBA$) ->
(A^3 X, {B:1, C:1}, BA$) ->
(A^3 X, {B:2, C:1}, A$) ->
(A^3 X, {B:2, C:1, A:1}, $) ->
(A^3 X B^2 C A, {$}, )

This version has at most O(|A|) (size of alphabet) overhead per input symbol and it does an optimal number of multiplications.

> **Comments:**
> **username_0**: To the downvoter: care to elaborate about the reason?  
> **username_1**: If I understand the algorithm, it is not optimal. For `AABB`, where A & B freely commute, your algorithm appears to require three multiplications, where only two are required (`let x=AB in xx`). I'm guessing the downvoter didn't like you presenting an answer without any attempt to justify its optimality.  
> **username_5**: I'm the downvoter.  Why should we believe your algorithm computes optimal results?  In particular, how does it optimize the number of multiplications needed to compute AAAAAAAAAAAAAAAAAAAAAAAAAAA?  (On the other hand, you haven't told us exactly what "optimal" means.)  
> **username_0**: Okay, you're right.  

---

