Discrete Fast Fourier Transform
Available code files:
- fft2.sage: implementation using vandermonde matrices illustrating the theory section below.
- fft3.sage: simple example with showing 3 steps of the algorithm.
- fft4.sage: illustrates the full working algorithm.
Suppose is an nth root of unity.
Recall: if then contains all nth roots of unity.
since vandermonde multiplication is simply evaluation of a polynomial.
Use and compute
Corollary: is invertible.
- Pointwise product
Finite Field Extension Containing Nth Roots of Unity
but is cyclic.
For all , there exists with ord.
Finding is sufficient for
FFT Algorithm Recursive Compute
We recurse to a depth of . Since each recursion uses , then in the final step , and we simply return .
We only need to prove a single step of the algorithm produces the desired result, and then the correctness is inductively proven.
Implementation of this algorithm is available in fft4.sage.
Particularly the function called
Write as the sum of two polynomials with equal degree
Let be the vector representations of
Let be the polynomials represented by the vectors
def calc_dft(ω_powers, f): m = len(f) if m == 1: return f g, h = vector(f[:m/2]), vector(f[m/2:]) r = g + h s = dot(g - h, ω_powers) ω_powers = vector(ω_i for ω_i in ω_powers[::2]) rT = calc_dft(ω_powers, r) sT = calc_dft(ω_powers, s) return list(alternate(rT, sT))
So then we can now compute for the even powers of .
For odd values
But observe that for any th root of unity and
Let be the representation for . Then we can see that as desired.
So then we can now compute for the odd powers of .
Let Now vectorize Compute reduced polynomials in vector form Convert them to polynomials from the vectors. We also expand them out below for completeness. Compute The values returned will be Which is the output we return.
Comparing Evaluations for and
We can see the evaluations are correct by substituting in .
We expect that on the domain produces the values , while on the same domain produces .
Let , be an even number. Then note that is a multiple of 2, so is a multiple of ,
For odd, we have a similar relation where , so . But observe that .