1
$\begingroup$

Polynomials in coefficient representation can be multiplied in $O(n \, log \,n)$ time by using a fast fourier transform to convolute the coefficients. The DFT of the coefficients correspond to the evaluation at the complex roots of unity. Is there an Intuition to this fact? I have previously only known fourier transforms as transforming a signal from the time domain to the frequency domain, so this connection is very strange to me.

$\endgroup$

1 Answer 1

1
$\begingroup$

Let

$$ p(x) = \sum_{n=0}^{N} a_n x^n. $$

Now consider setting $x$ to each of the $N$ complex roots of unity. For $x=\exp\left({j2\pi/N\cdot 0}\right)$, we get

$$ p(e^{j2\pi/N\cdot 0}) = \sum_{n=0}^{N} a_n \left( e^{j2\pi/N\cdot 0 } \right)^n. $$

For $x=\exp\left({j2\pi/N\cdot 1}\right)$, we get

$$ p(e^{j2\pi/N\cdot 1}) = \sum_{n=0}^{N} a_n \left( e^{j2\pi/N\cdot 1 } \right)^n. $$

In general, the polynomial evaluated at the $m^\mathrm{th}$ complex root of unity is

$$ p(e^{j2\pi/N\cdot m}) = \sum_{n=0}^{N} a_n \left( e^{j2\pi/N\cdot m } \right)^n = \sum_{n=0}^{N} a_n e^{j2\pi n m /N } $$

Note that the right hand side of this is the definition of the DFT of the sequence $a_n$.

$\endgroup$
1
  • 1
    $\begingroup$ I think in the last equality, in the middle part, you forgot to write the "power to n". $\endgroup$ Jan 12 at 6:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .