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