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