Re: Minimize number of mulitplications

*To*: mathgroup at smc.vnet.net*Subject*: [mg23840] Re: [mg23818] Minimize number of mulitplications*From*: Wagner Truppel <wtruppel at uci.edu>*Date*: Mon, 12 Jun 2000 01:17:32 -0400 (EDT)*References*: <200006100700.DAA13076@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Off the top of my head I don't remember any general algorithms for minimizing the number of multiplications given a set of general expressions. However, there is a standard method to determine the order in which you should multiply a set of matrices so as to minimize the number of multiplications. It makes use of what's referred to as a dynamic programming algorithm and can be found in any good book on algorithms (eg, "Introduction to Algorithms" by Cormen, Leiserson and Rivest). A Mathematica implementation is found in David Wagner's "Power Programming with Mathematica, The Kernel". Now, you can convert your example problem into one of matrix multiplication, as follows: (ax+b) (cx+d) = (a b) [x 1] (x 1) [c d] where () is a row vector and [] is a column vector. I suppose you could try the same trick for higher-order polynomials and then apply the dynamic programming algorithm I refer to above. Hope this helps. Wagner At 3:00 AM -0400 on 6/10/00, Jihad Haddad wrote: >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)

**References**:**Minimize number of mulitplications***From:*Jihad Haddad <jihad@imada.sdu.dk>