Services & ResourcesWolfram ForumsMathGroup Archive

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

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>