[Solved]: An $O(n)$ algorithm to FFT-evaluate an FFT evaluation

Problem Detail: 

This question is from a practice exam in my algorithms class. I'm posting the question and the answer listed in that practice exam:

Let $W$ be an $n\times n$ matrix whose $(i,j)$-th entry is $\omega_n^{ij}$, where $\omega_n$ is a principal $n$th root of unity. Let $X=(X_0,\dots,X_{n-1})$ be an $n$-vector. The product $W \times X$ can be computed in $O(n\log n)$ time. Let $FFT(X)$ denote the vector that results by applying the FFT evaluation algorithm to the vector $X$.

Describe an $O(n)$ algorithm to compute $FFT(FFT(x))$.

Answer: $FFT(FFT(x))$ is $W^2\times X$
$(W^2)_{jk} = 0$ if $j+k$ is not a multiple of $n$, and $n$ otherwise.

I'm confused about everything:
1. How does this run in $O(n)$? To compute $(W^2)_{jk}$ I'm already iterating through $n^2$ elements....
2. Why is $FFT(FFT(x)) = W^2\times X$?
3. Why is $(W^2)_{jk} = 0$ if $j+k$ is not a multiple of $n$, $n$ otherwise?

I would appreciate an answer that isn't too advanced as my math skills are limited to basic undergrad math classes of an engineering major.

Asked By : cs-newbie

Answered By : Yuval Filmus

Let's answer your questions one by one.

1. You don't compute $W^2$ by squaring $W$ algorithmically. Rather, you compute $W^2$ "on paper", and you find out a formula for $W^2$. Given this formula, you can check that $$ (W^2 X)_j = \sum_{k=0}^{n-1} (W^2)_{jk} X_k = nX_{-j}, $$ where $-j$ is the unique $k$ such that $j+k$ is a multiple of $n$. For example, if $n = 5$ then the correspondence between $j$ and $k$ is $$ \begin{array}{c|c} j & k \\\hline 0 & 0 \\ 1 & 4 \\ 2 & 3 \\ 3 & 2 \\ 4 & 1 \end{array} $$ Let $Y = W^2X$. Then $Y_j = nX_{-j}$, and so we can compute $Y$ from $X$ in linear time $O(n)$.

2. Since $FFT(X) = W\times X$, $FFT(FFT(X)) = W\times FFT(X) = W \times (W \times X) = (W \times W) \times X = W^2 \times X$.

3. This is a calculation: $$ \begin{align*} W^2_{jk} &= \sum_{i=0}^{n-1} W_{ji} W_{ik} \\ &= \sum_{i=0}^{n-1} \omega_n^{ji} \omega_n^{ik} \\ &= \sum_{i=0}^{n-1} \omega_n^{i(j+k)} \\ &= \sum_{i=0}^{n-1} (\omega_n^{j+k})^i. \end{align*} $$ If $j+k$ is a multiple of $n$ then $\omega_n^{j+k} = 1$ and so $$ W^2_{jk} = \sum_{i=0}^{n-1} 1^{j+k} = \sum_{i=0}^{n-1} 1 = n. $$ Otherwise, $\omega_n^{j+k} \neq 1$ and so we can use the formula for the sum of a geometric series to conclude $$ W^2_{jk} = \sum_{i=0}^{n-1} (\omega_n^{j+k})^i = \frac{(\omega_n^{j+k})^n - 1}{\omega_n^{j+k} - 1} = 0 $$ since $\omega_n^{(j+k)n} = (\omega_n^n)^{j+k} = 1^{j+k} = 1$.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents