fftinv

Function: fftinv
Section: polynomials
C-Name: FFTinv
Prototype: GG
Help: fftinv(w,P): given w from rootsof1, return the inverse Fourier transform
 of P.
Doc: Let $w=[1,z,\ldots,z^{N-1}]$ from some primitive $N$-roots of unity $z$
 where $N$ is a power of $2$, and $P$ be a polynomial $< N$,
 return the unnormalized discrete Fourier transform of $P$,
 $\{ P(1 / w[i]), 1 \leq i \leq N\}$. Also allow $P$ to be a vector
 $[p_0,\dots,p_n]$ representing the polynomial $\sum p_i X^i$. Composing
 \kbd{fft} and \kbd{fftinv} returns $N$ times the original input coefficients.
 \bprog
 ? w = rootsof1(4); fft(w, x^3+x+1)
 %1 = [3, 1, -1, 1]
 ? fftinv(w, %)
 %2 = [4, 4, 0, 4]
 ? Polrev(%) / 4
 %3 = x^3 + x + 1

 ? N = 512; w = rootsof1(N); T = random(1000 * x^(N-1));
 ? U = fft(w, T);
 time = 3 ms.
 ? V = vector(N, i, subst(T, 'x, w[i]));
 time = 65 ms.
 ? exponent(V - U)
 %7 = -97
 ? round(Polrev(fftinv(w,U) / N)) == T
 %8 = 1
 @eprog