Roots-of-unity orthogonality and radix-two FFT cost

For $0\le j,\mathrm{\ell }<M$, the $(j,\mathrm{\ell })$ entry of $F^{\ast }F$ is ${\sum }_{k=0}^{M-1}{\omega }^{(\mathrm{\ell }-j)k}$. If $j=\mathrm{\ell }$, this sum is $M$. Otherwise ${\omega }^{\mathrm{\ell }-j}\mathrm{\ne }1$ and the finite geometric-sum identity gives ${\sum }_{k=0}^{M-1}{\omega }^{(\mathrm{\ell }-j)k}=(1-{\omega }^{M(\mathrm{\ell }-j)})\mathrm{/}(1-{\omega }^{\mathrm{\ell }-j})=0$. Thus $F^{\ast }F=MI$, which gives the asserted inverse.

Splitting the DFT sum into even and odd indices gives $E_k+{\omega }^k{O}_k$ for $0\le k<M\mathrm{/}2$. For frequency $k+M\mathrm{/}2$, the even factor is unchanged because ${\omega }^{jM}=1$, while the odd factor changes sign because ${\omega }^{M\mathrm{/}2}=-1$. Therefore the outputs in [F1] are exactly the defining DFT sums. Induction on $q$, starting with $M=1$, proves exactness of the recursion.

At length $M>1$, forming both half-length transforms and combining their $M$ outputs costs at most $cM$ arithmetic operations for an absolute constant $c$. Hence $T(M)\le 2T(M\mathrm{/}2)+cM$ and $T(1)=O(1)$; expanding this recurrence for $q={\log }_{2}M$ levels gives $T(M)=O(M\log (2+M))$. The input, output, and one level of butterflies require $O(M)$ workspace; the inverse has the same cost plus coordinatewise scaling by $1\mathrm{/}M$.

Let $f,g$ have degree less than $n$, and choose $M^{\mathrm{\prime }}=2^{\lceil {\log }_2(2n-1)\rceil }$. Pad their coefficient lists to length $M^{\mathrm{\prime }}$, apply the forward DFT, multiply corresponding transformed coordinates, and apply the inverse DFT. For coefficient index $s$, the inverse-transform formula expands it as ${\sum }_{j,\mathrm{\ell }}{f}_j{g}_{\mathrm{\ell }}{M}^{\mathrm{\prime }-1}{\sum }_{k=0}^{M^{\mathrm{\prime }}-1}{\omega }^{(j+\mathrm{\ell }-s)k}$; step 1.1 makes the inner sum one exactly when $j+\mathrm{\ell }\equiv s(\mathrm{m}\mathrm{o}\mathrm{d}{M}^{\mathrm{\prime }})$ and zero otherwise. Thus the result is cyclic convolution modulo $z^{M^{\mathrm{\prime }}}-1$. The ordinary product has degree at most $2n-2<M^{\mathrm{\prime }}$, so no coefficient wraps around and the result is the exact polynomial product. Since $2n-1\le M^{\mathrm{\prime }}<2(2n-1)$ when $n>1$ (and $M^{\mathrm{\prime }}=1$ when $n=1$), step 3.1 gives $O(n\log (2+n))$ operations and $O(n)$ space.