How to evaluate all derivatives of a polynomial at a point with FFT? I found this problem:


  Evaluating all derivatives of a polynomial at a point
  
  Given a polynomial A(x) of degree-bound n, its tth derivative is
  defined by
  
  
  
  From the coefficient representation $(a_0, a_1, . . . , a_{n-1})$ of A(x) and
  a given point $x_0$, we wish to determine A(t) ($x_0$) for t = 0, 1, . . . ,
  n - 1.


I know the vector of the coefficients has to be used and I also know that the derivative of a term $ax^n$ is $a*n*x^{n-1}$, but where do I go from there?

I can only think of the naïve scheme to evaluate this: Find the first derivative ($O(n)$), evaluate it using Horner's method ($O(n)$). Repeat this for all deterivaties, giving $(O(n^2)$).
Hint: Taking the derivative has a certain, simple diagonal effect on the Fourier transform, that hopefully was covered in class. Hence if you compute the Fourier transform of the original function, you "know" the Fourier transform of all its derivatives as well. Given the Fourier transform, there is a formula for the value of the actual function. In your case, in order to compute the value of all derivatives of the function at a point, you multiply some matrix by the vector of Fourier coefficients. This matrix looks suspiciously similar to the DFT matrix, so hopefully you can compute the matrix-vector product in time $O(n\log n)$.