NEW SOUTH WALES
Algorithms COMP3121/9101
School of Computer Science and Engineering University of New South Wales
5. THE FAST FOURIER TRANSFORM
COMP3121/9101 1 / 32
Our strategy to multiply polynomials fast:
Given two polynomials of degree at most n,
PA(x)=Anxn +…+A0; PB(x)=Bnxn +…+B0
1 convert them into value representation at 2n + 1 distinct points x0,x1,…,x2n:
PA(x) ↔ {(x0, PA(x0)), (x1, PA(x1)), . . . , (x2n, PA(x2n))}
PB(x) ↔ {(x0,PB(x0)),(x1,PB(x1)),…,(x2n,PB(x2n))}
2 multiply them point by point using 2n + 1 multiplications:
(x0,PA(x0)PB(x0)), (x1,PA(x1)PB(x1)),…,(x2n,PA(x2n)PB(x2n))
PC (x0) PC (x1) PC (x2n)
3 Convert such value representation of PC(x) to its coefficient form
PC(x)=C2nx2n +C2n−1x2n−1 +…+C1x+C0;
Key Question: What values should we take for x0 , . . . , x2n to avoid “explosion” of size when we evaluate xni while computing PA(xi)=A0 +A1x+…+Anxni ?
COMP3121/9101 2 / 32
Complex numbers revisited
√ Complex numbers z = a + ib can be represented using their modulus |z| = a2 + b2
and their argument, arg(z), which is an angle taking values in (−π, π] and satisfying: z=|z|eiarg(z) =|z|(cosarg(z)+isinarg(z)),
see figure below.
!
z!=!a!+!i!b!
|z|!
arg!(z)!
b!
a!
COMP3121/9101
3 / 32
Complex numbers revisited
Recall that
z
= |z|
(cos(n arg(z)) + i sin(n arg(z))),
= see the figure.
e
n
i arg(z)n |z|e
= |z|
!
n inarg(z) n
z2!
|z|2!
z! 2!arg!(z)!
COMP3121/9101
4 / 32
Complex roots of unity
Roots of unity of order n are complex numbers which satisfy zn = 1. If zn = |z|n(cos(n arg(z)) + i sin(n arg(z))) = 1 then
|z| = 1 and n arg(z) is a multiple of 2π;
Thus, n arg(z) = 2π k, i.e., arg(z) = 2π k
n
We denote ωn = ei 2π/n; such ωn is called a primitive root of unity of order n.
!
!! = !!!!!!/!! |!!| = 1!
2!/!!
1!
(ω16)5
(ω16)4 (ω16)3
(ω16)2 ω16
1=(ω16)0
(ω16)15
(ω16)8
A root of unity ω of order n is primitive if all other roots of unity of the same order can be obtained as its powers ωk.
Roots of unity of order 16
COMP3121/9101 5 / 32
Complex roots of unity
Forωn =ei2π/n andforallksuchthat0≤k≤n−1, ((ωn)k)n = (ωn)n k = ((ωn)n)k = 1k = 1.
Thus, ωnk = (ωn)k is also a root of unity (and it can be shown that it is primitive just in case k is relatively prime with n).
Since ωnk are roots of unity for k = 0,1,…,n − 1 and there are at most n
distinct roots of unity of order n (i.e., solutions to the equation xn − 1 = 0) we
conclude that every root of unity of order n must be of the form ωnk.
For the product of any two roots of unity ωnk and ωnm of the same order we
haveωkωm =ωk+m. nnn
If k + m ≥ n then k + m = n + l for l = (k + m) mod n and we have ωkωm =ωk+m =ωn+l =ωnωl =1·ωl =ωl where0≤l