4

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

jkff
  • 8,941
  • 3
  • 23
  • 33
  • What is your cost model? Is "AABC" meant to be more efficient that "CAAB"? – Charles Stewart Sep 09 '10 at 08:09
  • My cost model is that I want to minimize the number of multiplications, but the multiplications themselves are equivalent in cost. – jkff Sep 09 '10 at 08:16
  • 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 Sep 09 '10 at 08:18
  • Yes of course, that's the point. See my own answer. – jkff Sep 09 '10 at 08:28
  • 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 Sep 09 '10 at 08:53
  • I think you meant "an associative binary operation". – jkff Sep 09 '10 at 09:34
  • 1
    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 Sep 09 '10 at 11:37
  • You're right; however, I think I'll be quite satisfied with the standard binary exponentiation. – jkff Sep 09 '10 at 11:49
  • 1
    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 Sep 09 '10 at 11:58
  • (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 Sep 09 '10 at 11:59
  • 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 Sep 09 '10 at 13:00
  • 3
    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 Sep 09 '10 at 14:01

1 Answers1

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

jkff
  • 8,941
  • 3
  • 23
  • 33
  • To the downvoter: care to elaborate about the reason? – jkff Sep 10 '10 at 05:28
  • 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 Sep 11 '10 at 14:48
  • 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ε Sep 12 '10 at 23:26
  • Okay, you're right. – jkff Sep 13 '10 at 17:41