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

Question

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.

Answer 1

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: \begin{equation} \widehat{(p_i\cdot p_j)} = \hat{p}_i[1,\dots,2d+1]\otimes \hat{p}_j[1,\dots,2d+1]. \end{equation}

• 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.