# How to compute $p(x)=\prod_{k=0}^{n-1}(x-z_k)$ using the FFT with complexity of O(nlog^2 n)?

I've a question and in its last step I'm required to find the above product (I need the coefficients of the result of that product as my final answer). It seems that FFT can be used to compute it. I read from texts that FFT has a complexity of nlogn. Since, it has asked for nlog^2 n, I assume that I've to do a divide and conquer on the product sequence (with a factor of 2). Without going into the details of how FFT works, can someone help me with the kind of input FFT accepts and output it gives out and how to use it for the product?

When I read something about FFT on the web, it shows stuff about signal processing, etc. I do not have sufficient knowledge to understand that. For example in this pdf http://www.robots.ox.ac.uk/~sjrob/Teaching/SP/l7.pdf, both DFT and FFT have been explained but I'm unable to figure out what exactly FFT takes as input and what output it gives. In other words, what does FFT calculate?

EDIT I read up on the FFT and I think I have an idea about how to implement this algorithm. I need some pointer regarding how to combine the individual results in the divide and conquer algorithm.

• FFT takes a sequence as it's input and returns a sequence as its output in the sense that it is a linear operator $F:\ell^{2}(\mathbb{Z}) \to \ell^{2}(\mathbb{Z})$. – Wavelet Aug 9 '16 at 19:12
• @Wavelet How is the output related to the input? What kind of change does it make to the input sequence? – aste123 Aug 9 '16 at 19:14
• Well it is just the discrete analog of the Fourier transform in continuous time so each value of the output sequence gives you the amplitude of a sinusoid of a particular frequency. The sinusoids of various frequencies are the basis functions of the decomposition, and the amplitude is the "contribution" of a given frequency to the function being decomposed. If that isn't clear enough let me know and I'll give a more detailed answer when I get a chance later this afternoon. – Wavelet Aug 9 '16 at 19:19
• @Wavelet I don't know what is discrete analog, continuous time, I do not even understand where the sine curve comes from, etc. Is it possible to learn FFT (and maybe DFT) only in terms of product and sum of polynomials without going into signals at all? – aste123 Aug 9 '16 at 19:30
• To expand a product of two polynomials is to convolve their coefficients. I figure you can use discrete Fourier transforms to somehow exploit the convolution theorem. – enthdegree Aug 9 '16 at 21:01

The DFT of a sample of length $N$ is another $N$-vector where the $n^{th}$ coefficient is the zero-delay cross-correlation of the sample with $[\exp(i\omega_n 0),\dots,\exp(i\omega_n (N-1))]$, $\omega_n = 2\pi \frac{n}{N}$, $n=0,\dots,N-1$.

Your problem is to compute all $N$ coefficients in the DFT in $\mathcal{O}(N\log^2N)$.

Use convolution theorem with divide-and-conquer. Here is the general principle:

• Say you have $N$ polynomials of the form $p_n(x)=c_n\cdot x^0+1\cdot x^1$, and the goal is to compute the coefficients of $\prod_1^Np_n$.

Denote $\hat{p}_n$ as the discrete function of coefficients of $p_n$, so in our case: \begin{align} \hat{p}_n&=[c_n,1,0,\dots], \\ \hat{p}_n[1,\dots, k] &= [\underset{k\text{ terms}}{\underbrace{c_n,1,0,\dots ,0}}]. \end{align}

By the distributive property, the coefficients of the product of two polynomials $p_i$ and $p_j$, both of degree $d$, equals the polynomial corresponding to the sequence: $$\widehat{(p_i\cdot p_j)} = \hat{p}_i[1,\dots,2d+1]\otimes \hat{p}_j[1,\dots,2d+1].$$

• The convolution theorem says that $\mathcal{F}(f \otimes g)= \mathcal{F}(f)\cdot \mathcal{F}(g)$ where $f,g$ are (discrete) functions, $\otimes$ is discrete convolution, $\mathcal{F}$ is the (discrete) Fourier transform and $\cdot$ is point/element-wise multiplication.

Here's what the algorithm might look like, assuming $N$ is a power of 2:

Start $K\leftarrow N$ polynomials $p_k (k=1,\dots,K)$ and degree $d\leftarrow 1.$

1. For $k=1,\dots, K$, let $\hat{q}_k\leftarrow \mathcal{F}(\hat{p}_k[1,\dots,2d+1])$. (Takes $\mathcal{O}(K\cdot d\cdot\log(d))$)
2. For $k=1,\dots, K/2,$ let $\hat{q}_k \leftarrow \hat{q}_{2k-1}\cdot \hat{q}_{2k}.$ (Takes $\mathcal{O}(K\cdot d)$)
3. For $k=1,\dots,K/2,$ let $\hat{p}_{k}\leftarrow \mathcal{F}^{-1}(\hat{q}_k).$ (Takes $\mathcal{O}(K\cdot d\cdot \log(d))$)
4. Stop if $K=1.$ Otherwise let $K\leftarrow K/2,\ d\leftarrow 2d,$ and go back to step 1.

After this completes, $\hat{p}_1$ has the coefficients of the product.

This will take: \begin{align} &\mathcal{O}\left(\sum_{\ell=1}^{\log(N)} \ell \cdot (2^{\ell-1}) \cdot \log(2^{\ell-1}) \right) \\ = & \mathcal{O}\left(\log(N)\cdot 2^{\log(N)-1} \cdot \log\left(2^{\log(N)-1}\right)\right) \\ = & \mathcal{O}\left(N\cdot \log(N)^2\right) \end{align} operations, just as needed.