1.  Fast Fourier Transforms (FFT)

1.1  motivation

Given a function there are several representations.

• polynomial: f(x) = a₀+a₁x+...a_n-1x^n-1
• point set: (0,f(0)),(1,f(1)),(2,f(2)),...(n-1),f(n-1))

The point set representation (with redundant sets) is used to transmit information in about a polynomial over a noisy channel. This message is decoded using a big matrix.

1	0	...	...	0
1	2	22	...	2n-1
.	.
.	.
1	cn	(cn)2	...	(cn)n-1

*

a0

.

.

.

an-1

=

f(0)

f(2)

.

.

f(cn)

This is O(n³) to solve, or perhaps O(n^2.36) if you are clever.

There is a case (the FFT case) which is quickly solvable.

1.2  vector convolution

The convolution of two vectors (a₀,...,a_n-1)Ä(h₀,...,h_n-1) = (c₀,...,c_2n-2) is defined by c_k = å_{i = 0}^ka_ib_k-i

1.3  algorithm

Compute f(x) at f(0),f(1),...,f(2n-2) and g(x) at g(0),...,g(2n-2) . Then, we calculate f(0)g(0),...,f(2n-2)g(2n-2) to get f(x)g(x) = c₀+c₁x+...c_2n-2x^2n-2 . This doesn't look like it works except that by shifting to the complex plane, everything can be made cheap.

1.4  definitions

w = primitive nth root of unity in the complex plane. In orther words w = e^i2pj/_n where j ¹ n .

Conditions:

• w ¹ 1
• w^p ¹ 1 with 1 £ p £ n-1
• wⁿ = 1
• å_{j = 0}^n-1w^jp = 0 for 1 £ p £ n-1

The discrete fourier transform is defined as:

1	.	.	.	1
.	w	w2	...
.	w2	w4	...
.
1	.	.	.	w

*

a0

.

.

.

an

=

f(w0)

.

.

.

f(wn-1)

We can express the matrix as DFT transform matrix as F_ij = w^ij

1.5  lemma

(F^-1)_ij = ¹/_nw^-ij

Proof:

multiply (F^-1)_ijF_jk using the property wⁿ = 1 and å_{j = 0}^n-1w^jp = 0 for 1 £ p £ n-1 .

1.6  FFT

Let

D_ⁿ/2 =

1
	w
		w2
			···
				-1

Then

F_nV =

Fn/2	Dn/2Fn/2
Fn/2	-Dn/2Fn/2

*

Veven

Vodd

This suggest the divide and conquer algorithm:

compute F_ⁿ/2V_even and D_ⁿ/2F_ⁿ/2V_odd , then construct F_nV and return.

1.6.1 timing

T(n) = 2*T(ⁿ/₂)+³/₂n which means T(n) = O(nlogn )

1.7  FFT in parallel

The FFT algorithm is parallelizable. Arrange the nodes of the parallel processor on a hypercube. Each node has a particular value associated with it. Have the node look at its first (bitwise ordering) neighbor. These 2 nodes will have values a and b . Give one node a+b and the other a-b . Repeat for each bit.

2.  Shuffle exchange graph

let V = {(a₀,...,a_n)|a_i = {0,1}}

then the 'shuffle' takes (a₀,...,a_n)® (a₁,...,a_na₀)

and the 'exchange' takes (a₀,...,a_n) = (ba₁,...,a_n)