Hi, math01-ga:
I'm not sure if you are still interested in an answer to this
question, since you expired a few others that went unanswered for a
few days.
"Divide-and-conquer" suggests an algorithm which is suitable for
parallel implmementation. In particular this phrase is often used for
recursive algorithms that split the input data (presumably the
polynomial coefficients in this case) into two more-or-less equal
subsets for processing, the results of which can then be recombined to
give the final output.
One such scheme that is easy to implement is to separate out the even
and odd degree terms of a polynomial, so that:
P(x) = x*Q(x^2) + E(x^2)
where E(x) is a polynomial of half the degree or less than P(x) which
collects its even terms as E(x^2), and similarly Q(x) is a smaller
degree polynomial such that x*Q(x^2) has all the odd terms of P(x).
The data needed to evaluate E(x^2) and Q(x^2) are disjoint, so this is
especially attractive for a distributed computation in which there
need be little "shared memory" between processors.
I'll let you work out the operation count, if you are still
interested. Note that the algorithm can be implemented on an ordinary
CPU architecture as a recursive procedure. The procedure computes x^2
(one multiplication), calls itself twice (on roughly half the size
inputs each time), and finally recombines the subprocedure outputs
using one addition and one multiplication.
From this description the overall operation count is easily found by
induction.
regards, mathtalk-ga |
