# Faster multiplication with a restricted set of multiplicands?

Let $A$ be a set of $k>1$ distinct elements from a semigroup. We wish to compute the product $$p=b_1 b_2 \cdots b_n$$ where each $b_i\in A$. Clearly $n-1$ multiplications suffice to compute $p$; can we do it with fewer?

Let $m=m(b_1,...,b_n)$ be the minimum number of multiplications required to compute $p$. My specific questions are:

1. Can we compute $m$ in polynomial time?
2. Can we answer question #1 constructively, i.e. actually figure out which $m$ terms can be multiplied together to compute $p$? If not, can we do it with some approximation guarantee (like "at worst we use $2m$ terms"?)

The interesting case (for my application, anyway) occurs when $n\gg k$ (so there are many common subexpressions) but the semigroup is noncommutative (so you cannot simply rearrange terms and use repeated doubling).

Let me outline one simple (but insufficient) approach. Suppose that we begin by computing all products of (not necessarily distinct) pairs from $A$. Then we can compute $p$ with $k^2+(\lceil n/2 \rceil -1)$ multiplications by multiplying the terms two at a time. If $k^2\ll n$, then we have essentially halved the number of multiplications. Analogous reasoning can be extended to provide roughly an $\lfloor \log_k(n)-\log_k(\log_k(n)) \rfloor -1$ improvement in the number of multiplications. However, for highly repetitive strings we could do much better still.

This problem arose in the context of parallel inference algorithms for hidden Markov models; the noncommutative semigroup in question consists of non-negative matrices over the reals.

• This smells NP-hard, but what do I know. You might try cstheory.stackexchange.com. – user57911 Sep 6 '14 at 7:27

## 2 Answers

This question has already been studied in the literature under the term "word chains". Doing a search on that term will turn up some relevant papers, such as

http://dl.acm.org/citation.cfm?id=33329

http://www.sciencedirect.com/science/article/pii/0020019089901671

http://dl.acm.org/citation.cfm?id=79917

Basically one cannot get a much better compression (in general) than the one you propose.

Caution: there is a different, unrelated problem also called "word chain" in the literature.

Addendum: Yu. V. Merekin has also worked on this problem, but to my knowledge it has only appeared in Russian.

http://www.mathnet.ru/php/person.phtml?personid=17890&option_lang=eng

Addendum 2: And finally, there is a complexity result here:

https://www.cs.virginia.edu/~shelat/papers/GrammarIEEE.pdf

although I never managed to understand the proof.

You can try a dynamic programming approach as in this example of optimal parenthesising chain products of matrices.

Specifically, build bottom-up dynamic programming table, as in the above example, by recording the "costs" of multiplications with different parenthesisations. The "cost" would be different than in the case of matrix chains, but the overall approach may work.

EDIT:

You may want to try suffix trees to identify repreated substrings. Suffix trees have been used in Lempel-Ziv compression algorithms, among other things.

LZ compression creates a "dictionary" of repeated patterns so that in the compressed output the repeated pattern would be replaced by a dictionary reference that contains it. At the decompression step you retrieve the pattern from the dictionary.

You can do something very similar, except that in the compression step you add the computed value of the pattern to the dictionary, and at the decompression step you retrieve that pre-computed value.

• I appreciate the suggestion, but I don't see how to construct the relevant dynamic program in this case (at least with a subexponential state space), since common subexpressions can occur anywhere in the string. But perhaps there is a cleverer way to pose the problem that I'm missing? – Bill Bradley Jan 8 '14 at 3:01
• @BillBradley: just added another approach to the answer, based on LZ encoding schemes. The reason: the core of the problem seems to be in efficient identification of repeated substrings. – Michael Jan 8 '14 at 19:47
• Those are both great suggestions, but I don't know how to extend them to proofs. Using LZ would be great (particularly since it's optimal for ergodic processes, which I have in my application), but the algorithm searches over arbitrary preceding subsequences, whereas we can only use precomputed subsequences. Suffix trees seem great (and it's also possible to construct "count suffix trees", which include substring frequencies, in linear time), but how do I use it? These feel like the right tools, but I'm missing something. – Bill Bradley Jan 9 '14 at 20:06