World's most popular travel blog for travel bloggers.

Calculating DFT of a specific polynomial

, , No Comments
Problem Detail: 

This seems like a simple problem but I'm getting the impression I'm missing something.

The problem

Given the values $v_1, v_2, \ldots, v_n$ such that $DFT_n(P(x)) = (v_1, v_2, \ldots, v_n) $ for $ P(x) = \sum\limits_{i=0}^k a_ix^i$ , $k < n$ - find $ DFT_{2n}(P(x^2)) $

My attempt:

First expand $P(x^2) $ : $$P(x^2) = a_0 + a_1x^2 + \ldots + a_k^{2k}$$ Let's denote by $W^j_n$ the j'th root of unity of order n. We have : $$ W^j_{2n} = e^\frac{2\pi ij}{2n} = e^\frac{\pi i j}{n}$$ Using this information, let's evaluate a term p of $P(x^2)$ on some $W^j_{2n}$ : $$a_p(x^2) = a_p(e^\frac{\pi ij}{n})^{2p} = a_p(e^{2\pi i}) ^\frac{jp}{n} = a_p$$ (since $e^{2\pi i} = 1$) So, when evaluating any term of the compound polynomial on some unity root of order 2n we get $\sum\limits_{i=0} ^k ak$ and therefore the final answer is: $$(\sum\limits_{i=0} ^k ak, \sum\limits_{i=0} ^k ak,\ldots, \sum\limits_{i=0} ^k ak)$$

This seems wrong, I don't even use the information about $(v_1, \ldots, v_n)$(should the answer be in terms of those?)

Any help would be appreciated.

Asked By : Kardom
Answered By : Yuval Filmus

You haven't explained what you mean by the DFT of a polynomial, so I'm assuming you mean the polynomial evaluated at all $n$th roots of unity, that is, $$ v_i = P(\omega^i), $$ where $\omega = e^{2\pi i/n}$ is a primitive $n$th root of unity. Let now $Q(x) = P(x^2)$, and let $\varpi = e^{\pi i/n}$ be a primitive $2n$th root of unity, $\varpi^2 = \omega$. Let us examine its DFT $w_1,\ldots,w_{2n}$: $$ w_k = Q(\varpi^k) = P(\varpi^{2k}) = P(\omega^k) = v_{k \mod{n}}. $$ We conclude that the DFT of $Q$ is $$ v_1,\ldots,v_n,v_1,\ldots,v_n. $$

Best Answer from StackOverflow

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

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback