[Date Index] [Thread Index] [Author Index]

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>