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).

  • $\begingroup$ What is your cost model? Is "AABC" meant to be more efficient that "CAAB"? $\endgroup$ Sep 9 '10 at 8:09
  • $\begingroup$ My cost model is that I want to minimize the number of multiplications, but the multiplications themselves are equivalent in cost. $\endgroup$
    – jkff
    Sep 9 '10 at 8:16
  • 1
    $\begingroup$ 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 cstheory.stackexchange.com/questions/912/…. 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. $\endgroup$ Sep 9 '10 at 11:37
  • 1
    $\begingroup$ 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) $\endgroup$ Sep 9 '10 at 11:58
  • 3
    $\begingroup$ 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. $\endgroup$ Sep 9 '10 at 14:01

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.


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.

  • $\begingroup$ To the downvoter: care to elaborate about the reason? $\endgroup$
    – jkff
    Sep 10 '10 at 5:28
  • $\begingroup$ 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. $\endgroup$ Sep 11 '10 at 14:48
  • $\begingroup$ 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.) $\endgroup$
    – Jeffε
    Sep 12 '10 at 23:26
  • $\begingroup$ Okay, you're right. $\endgroup$
    – jkff
    Sep 13 '10 at 17:41

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.