Minimize number of mulitplications

*To*: mathgroup at smc.vnet.net*Subject*: [mg23818] Minimize number of mulitplications*From*: Jihad Haddad <jihad at imada.sdu.dk>*Date*: Sat, 10 Jun 2000 03:00:26 -0400 (EDT)*Organization*: UNI-C*Sender*: owner-wri-mathgroup at wolfram.com

I am sitting in the middle of my thesis and bumped into the following problem which I hope Mathematica has a solution for. Or maybe there exists a package I can download that can solve it. I can illustrate it with a simple problem, even though my problem is of a much larger magnitude. Multiplying two first degree polynomials (ax+b) and (cx+d) yields the following 2nd degree polynomial: (ac)x^2 + (ad+bc)x + bd. So to compute the second degree polynomial given the two first degree polynomials we have to compute the three expressions (ac), (ad+bc) and (bd). Intuitively that will take four multiplications to perform, namely (a*c), (a*d), (b*c) and (b*d). My aim is to minimize the number of multiplications, and in the case above, it is possible to compute the three expressions in three multiplications. We can find (a*c), (b*d) and (a+b)*(c+d). That is three multiplications. But we still need the expression (ad+bc). But that is equal to (a+b)*(c+d)-(a*c)-(b*d) which we already have computed. Note that I do not care how many additions and subtractions I perform. That is because multiplications are a lot more time consuming than additions or subtractions. Now the question is: Is there a Mathematica function that can find the minimal number of multiplications to compute a certain number of expressions, given the expressions? I will be very glad to get an answer. I am in desperate need for such an optimizing function. Thank you in advance Jihad Haddad (Denmark)

**Follow-Ups**:**Re: Minimize number of mulitplications***From:*Wagner Truppel <wtruppel@uci.edu>