[Solved]: How to evaluate all derivatives of a polynomial at a point with FFT?

Problem Detail: 

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

Asked By : cs-newbie

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24314

 Ask a Question

 Download Related Notes/Documents