"Tree" for Fast Fourier Transform polynomial evaluation?

Question

I am trying to evaluate polynomial A(x) through a divide and conquer algorithm using the FFT. I basically break the polynomial into its odd roots and even roots and then recurse on the two smaller polynomials.(allowing me to evaluate twice the number values per recursion).

To visualize this, I am trying to create a tree to show the polynomial's path through the algorithm. I am not exactly sure how to get started- could someone just start me off? I am not expecting a complete tree just a brief example to get me on the right path.

Answer 1

Here is a simple example from Chapter 2 of Algorithms:

A(x) = 3 + 4x + 6x^2 + 2x^3 + x^4 + 10x^5
     = (3 + 6x^2 + x^4) + x(4 + 2x^2 + 10x^4)
     = E(x^2) + x*O(x^2)

where

E(x) = 3 + 6x + x^2
O(x) = 4 + 2x + 10x^2

Notice how the size of the polynomial has shrunk by a factor of 2? Also, we can recycle an evaluation at x since -x will result in a similar value.

A(x) = E(x^2) + x*O(x^2)
A(-x) = E(x^2) - x*O(x^2)

I hope you can see how this recursive process becomes a tree.