NEW SOUTH WALES
Algorithms COMP3121/9101
Aleks Ignjatovi ́c
School of Computer Science and Engineering University of New South Wales
5. THE FAST FOURIER TRANSFORM (not examinable material)
COMP3121/9101 1 / 33
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;
COMP3121/9101 2 / 33
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;
COMP3121/9101 2 / 33
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;
COMP3121/9101 2 / 33
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;
COMP3121/9101 2 / 33
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;
COMP3121/9101 2 / 33
Our strategy to multiply polynomials fast:
So,weneed2n+1valuesofPA(xi)andPB(xi), 0≤i≤2n.
If we use 2n + 1 integers which are the smallest by their absolute value, i.e.,
−n,−(n − 1),…,−1,0,1,…,n − 1,n among the values which we need to compute is
PA(n)=A0 +A1n+…+An−1nn−1 +Annn
We saw that the trouble is that, as the degree n of the polynomials PA(x) and PB(x) increases, the value of nn increases very fast and causes rapid increase of the computational complexity of the algorithm for polynomial multiplication which we used in the generalised Karatsuba algorithm.
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 3 / 33
Our strategy to multiply polynomials fast:
So,weneed2n+1valuesofPA(xi)andPB(xi), 0≤i≤2n.
If we use 2n + 1 integers which are the smallest by their absolute value, i.e.,
−n,−(n − 1),…,−1,0,1,…,n − 1,n among the values which we need to compute is
PA(n)=A0 +A1n+…+An−1nn−1 +Annn
We saw that the trouble is that, as the degree n of the polynomials PA(x) and PB(x) increases, the value of nn increases very fast and causes rapid increase of the computational complexity of the algorithm for polynomial multiplication which we used in the generalised Karatsuba algorithm.
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 3 / 33
Our strategy to multiply polynomials fast:
So,weneed2n+1valuesofPA(xi)andPB(xi), 0≤i≤2n.
If we use 2n + 1 integers which are the smallest by their absolute value, i.e.,
−n,−(n − 1),…,−1,0,1,…,n − 1,n among the values which we need to compute is
PA(n)=A0 +A1n+…+An−1nn−1 +Annn
We saw that the trouble is that, as the degree n of the polynomials PA(x) and PB(x) increases, the value of nn increases very fast and causes rapid increase of the computational complexity of the algorithm for polynomial multiplication which we used in the generalised Karatsuba algorithm.
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 3 / 33
Our strategy to multiply polynomials fast:
So,weneed2n+1valuesofPA(xi)andPB(xi), 0≤i≤2n.
If we use 2n + 1 integers which are the smallest by their absolute value, i.e.,
−n,−(n − 1),…,−1,0,1,…,n − 1,n among the values which we need to compute is
PA(n)=A0 +A1n+…+An−1nn−1 +Annn
We saw that the trouble is that, as the degree n of the polynomials PA(x) and PB(x) increases, the value of nn increases very fast and causes rapid increase of the computational complexity of the algorithm for polynomial multiplication which we used in the generalised Karatsuba algorithm.
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 3 / 33
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
4 / 33
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
5 / 33
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 an integer 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 6 / 33
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 an integer 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 6 / 33
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 an integer 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 6 / 33
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 an integer 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 6 / 33
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 an integer 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 6 / 33
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