MathGroup Archive 2000

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

Search the Archive

Re: Minimize number of mulitplications

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.

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

  • Prev by Date: Re: ContourPlot doesn't work properly?
  • Next by Date: Re: Pattern Matching
  • Previous by thread: Minimize number of mulitplications
  • Next by thread: Derivative of Root objects