# 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.

## Theory

Complexity:

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.

### Lemma:

Use and compute

Corollary: is invertible.

### Definitions

1. Convolution
2. 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.

### Algorithm

Implementation of this algorithm is available in fft4.sage. Particularly the function called calc_dft().

function DFT()
if then
return
end
Write as the sum of two polynomials with equal degree

Let be the vector representations of

Let be the polynomials represented by the vectors

Compute
Compute

return
end

Sage code:

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))


### Even Values

So then we can now compute for the even powers of .

### Odd Values

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 .

## Example

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 .

#### Even Values

Let , be an even number. Then note that is a multiple of 2, so is a multiple of ,

#### Odd Values

For odd, we have a similar relation where , so . But observe that .