patternMinor
An $O(n)$ algorithm to FFT-evaluate an FFT evaluation
Viewed 0 times
algorithmevaluationfftevaluate
Problem
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:
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.
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:
- How does this run in $O(n)$? To compute $(W^2)_{jk}$ I'm already iterating through $n^2$ elements....
- Why is $FFT(FFT(x)) = W^2\times X$?
- 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.
Solution
Let's answer your questions one by one.
-
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)$.
-
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$.
-
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$.
-
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)$.
-
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$.
-
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$.
Context
StackExchange Computer Science Q#24269, answer score: 4
Revisions (0)
No revisions yet.