## Minimising the Number of Multiplications

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

### Minimising the Number of Multiplications

I'm looking for an algorithm that will optimally solve the following problem: given a finite set of variables, V = {a, b, c, ... } and a finite set of products of those variables P = {P1, P2, P3, ...}, what is the minimal number of multiplications required to calculate all the elements of P, and what is the algorithm for calculating the elements of P?

So, for instance, if I have V = {a, b, c, d} and P = { abc, abd } then you only need 3 multiplications, one to find A = ab, and one each to find Ac and Ad.

I expect that someone has already done a fair bit of work on this problem, so a few references would be great, though a reasonably efficient algorithm would be better.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jestingrabbit

Posts: 5388
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Minimising the Number of Multiplications

I don't have any references for you, but I suspect it is an NP-complete problem. If your products allow variables to be repeated, then it definitely is because exponentiation with minimal multiplications is already NP-complete. See for example this wiki page.

jaap

Posts: 1770
Joined: Fri Jul 06, 2007 7:06 am UTC

### Re: Minimising the Number of Multiplications

I think the algorithmic time will be exponential unless |P| grows exponentially to |V|.
The number of terms in the final answer will grow proportionally to 2^n, and if |P| does not grow exponentially to |V|, the number of multiplications required will overall grow exponentially.
Ankit1010

Posts: 135
Joined: Fri Feb 11, 2011 11:32 am UTC

### Re: Minimising the Number of Multiplications

It seems to me that all you need do is modify the find-all-subsets routine to create, store and reuse the partial products as the subset is being generated. Not that hard. Since finding all subsets is a NP problem, this would be too.

shawnhcorey

Posts: 42
Joined: Sun Jan 08, 2012 2:08 pm UTC

### Re: Minimising the Number of Multiplications

Perhaps not a complete solution, but you might want to have a look into frequent itemset mining.
Feel free to call me Julian. J+ is just an abbreviation.
coding and xkcd combined

Jplus

Posts: 1289
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: classified

### Re: Minimising the Number of Multiplications

jaap wrote:I don't have any references for you, but I suspect it is an NP-complete problem. If your products allow variables to be repeated, then it definitely is because exponentiation with minimal multiplications is already NP-complete. See for example this wiki page.

That WP page is a pretty good one. Section 6 of the below pdf seems to be what I'm after, though I haven't checked all the details yet.

http://cr.yp.to/papers/pippenger.pdf

Thanks.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jestingrabbit

Posts: 5388
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Minimising the Number of Multiplications

I thought I'd add an ending to the story, because it ended pretty well. The actual products that I had to calculate were of n+2 things each, and there were n+1 of them, so naively it would have cost (n+1)^2 multiplications. In the end though, using some cunning, I go it down to an upper bound of 9n/2.

So, optimisation dreams do happen!
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jestingrabbit

Posts: 5388
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney