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

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

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

jaap
Posts: 2091
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

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

Ankit1010
Posts: 135
Joined: Fri Feb 11, 2011 11:32 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.

shawnhcorey
Posts: 42
Joined: Sun Jan 08, 2012 2:08 pm 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.

Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

### Re: Minimising the Number of Multiplications

Perhaps not a complete solution, but you might want to have a look into frequent itemset mining.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### 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
Factoids are just Datas that haven't grown up yet
Posts: 5967
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.