Lecture 30: Fast Fourier transform

IIT Kanpur July 201
20 followers
Sep 6, 2024
[Music]
uh welcome uh so in the last
lecture uh we were
talking about uh how to compute the four
year coefficient of a function with
which is defined on Jen and the number
of steps One require to do the
simple uh calculation of multiplication
and
addition in a computer is going to do
addition and multiplication so how many
steps needed to compute a for your
transform that is uh very important uh
for many if you want to compute the for
transform
precisely so what we have seen is that
if I take a uh function f and I write it
in terms of the F0 fub1 FN minus1 and
the fourar coefficient to be Capital F0
to FN minus of one then as a matrix what
we have seen the script F when it acts
on the column Vector F0 to FN minus of
one this is is going to land us into the
foror coefficient of the function f and
that what we have seen is that it will
be kind of the order n² + 2 N at most I
mean that is what we can do it if we
multiply if we take each step
multiplication as one step and each
addition as one step then if we compute
it this n cross n Matrix and so we will
get of the order of n square at least so
now so just imagine that if n square and
if you have a large data you need to
find the for your coefficient then it it
will take enormous amount of time for
the computer to compute the forer
coefficients so there is a clever method
given by K and
toi uh that for certain cases one can
can
reduce this number of Step actually
after their uh algorithm
so uh life becomes
much easier to
compute so we'll we'll see the that so
now what is the essence of their idea so
now we have seen in the last lecture
this is what is
our 4 year
coefficient we can write it in terms of
the operator F act script F acting on F
we are going to get the forer
coefficients okay so now uh let's uh
play around a bit so now I
Define
uh two functions I will write
fub1 fub1 to be equal to
just I will take
the odd and even divide it so this is f
of 2 this is zero so this suppose I have
N I am getting 2 m so this is f of 2 m -
2 and
0 and I write similarly F2 to be equal
to
0
F1
0
F3 0 like this then zero and this is f
of 2 m minus of 1 clearly if we see F
our function is nothing but fub1 +
FS2 and similarly what we would like
to define the script
F1 to be equal to 1 by 2
m and this is 1 0 1
1
1 and then this is 0
0 0 this is
uh
1 Omega squ
then Omega to the power 2
into 2 m -
1 and then again 0 0 and then the the
last but one column will have the last
column will have zero this is 1 Omega to
the^ 2 m - 2 and this is
Omega to the power M - 2 m
-1
uh 2 m -
2 and uh we denote similarly F2
as 1
/ 2
m and then this is 0 0 1 Omega Omega SAR
and then this goes
to then 0 0 0 and then here in the last
column would be Omega 2 m
-1 Omega 2 into 2 m
-1 and this goes
to then if I if you can can see that uh
if you are acting fub1 with
FS2 now if you act fub1 with FS2 that we
know that this is equal to zero and
similarly FS2 if it acts on fub1 this is
equal to zero and also notice that f is
equal to fub1 +
F2
so therefore
uh
f 1 F1 + F2 F2 this is equal to our
forear coefficient so in a sense what we
can see that we
are reduce what essentially when I am
acting the script F1 on F I am although
it is uh a part of the 2 m cross to a
matrix but uh I can treat this that as a
function on Z M instead of Z2 M
similarly for FS2 that means the number
of uh if uh the number of computing the
forer coefficient it is going to
be let's say if I denote it by for
JM this then what it suggest is that if
I take 2 m z
2m then number what I
need this is essentially less or equal
to here this is the M4 coefficient here
I am going to a for your coefficient
with little bit of extra
multiplication and uh so therefore this
is some comparable to 2 * number of M
and plus something so that what we can
easily you can do it by Computing but
we'll write it down very
explicitly so a good reference for these
materials is the book A F course in
foror analysis by David W
camer now let us uh look at this so now
I will say the LMA
let gal of M
denotes the minimum number
of minimum number
of the operation
needed to
calculate
all the four year coefficients
of any
function
on
ZM
then the
number I need to calculate the forar
coefficient for a function on J2 m is
less or equal to 2 * the number
of
m+ 8
m
so so the proof one can see it you take
let's do Omega 2 m i will denote it as e
to the power for - 2 < I by 2
m
okay now
first I need to compute Omega 2 m Omega
2
m²
and this is Omega 2 m 2 m minus of 1
this will require how many stat 2 m
steps okay two 2 m multiplication so
this is 2 m rather to be more precise 2
m
multiplications okay now we know that so
if Omega M this is equal to e^ - 2 piun
I I by m e^ - 2 piun
I 2 by 2 m which is equal to Omega 2
m² so now we can we can compute the fub1
and FS2 by at most 2 m addition and
multiplications now let's calculate uh
our forar coefficient f K by the
definition of that this is equal to 1 by
2 because 1 by 2 m and this so this is
equal to F1 of
K the even part plus
f 2 of
K Omega 2 m to the power K why is that
now just you calculate the simple
calculation this is 1 by 2 2 m then the
summation Over N = 0 to 2 m minus of 1
this is f of K F of n e to the power -
2i i k n by 2 m this is what we need to
calculate so this sum I can write it as
1 by 2 this is 1 by
m
summation / n is = to 0
to
uh M
-1 and F
of 2 N and e to the power - 2i i k 2 N
by uh 2 m + 1 by m summation n is = 0 to
M - 1
F of 2 n + 1 and then e^ - 2 piun i k 2
n + 1 by 2
m so which Ence if you write this down
then this is going to
be 1 /
M summation n is = 0 to n
-1 this is our F1 at n and then this is
e the^ - 2i i k n ided by m the factor
of two gets
cancell
plus 1 by
m summation / n is = 0 to M
-1 F2 of
N and then e to the power - 2i i k n by
m into e^ - 2 piun i k by 2
m so this is what precisely what we have
written down over there so this is
nothing but 1 by 2 and then this is fub1
of K plus F2 of K and then Omega 2 m to
the power
K that's what it is uh going to be so
now as you can see that FK can be
computed
than uh at most one addition and two
multiplication this is one addition and
two multiplication that is what it is
going to therefore hence the cardinality
of the number of multiplication and
addition required for J2 M this is less
or equal to so now F1 I need to get M
because I am Computing the for I'm
assuming that the this is the number in
which I can compute for JM so this is 2
* number of M then this is the 3 into 2
that is the 6 M and plus when we are
calculating this 2 m multiplication so
this will give us 8 m so that's what the
LMA is saying so now the number of 2 m
so now as you can see that if you are
taking the 2 m uh so we going to
get this so now this has a wonderful
effect which is called the
fast for year
transform more popularly known as
fftt okay so what does it say so this
says that you
take this
theorem given
Omega n this is equal to e^ - 2 pi I by
n
with n I am taking 2 The Power n this is
this works for particular if our n is of
the form 2 the^ N where N is a non-
negative
integer so n = 1
and
onwards positive integer it is
possible to
calculate the forer coefficient
of a
function on
ZN
with at
most 4 into 2 ^ n into n which is
nothing
but uh 4 2 ^ n is capital n and n is
nothing but log 2 to the base
n so this is a
drastical step now for example if you
want to take suppose uh uh let's say
let's compare this suppose if I am
taking n
uh is equal to 2 the^
16 then in our earlier one one would
like to get that this is going to be 2
the^ 32 so at least this 2 ^ 32 is equal
to
65,536 however if I calculate this so
this is 4 into
2^ 16 into n is 16 that means 2^
16 into uh
2^ uh 16 isal to
this and uh 2 ^ 16 into 64 so instead of
going to
65,536 steps are needed if we just do
with the multiplication matrix
multiplication with the F and then find
out all the four year coefficient so
this is a very clever trick and very
efficient trick which
actually uh makes the computation
possible so the proof is by induction
now for n =
1 now that means what what is we are
doing in Z2 so which is equal to 0 and 1
now if you calculate F0 then this is F0
+ f of 1 now if I calculate
F1 uh this is of course half of
this and fub1 then this is going to be
12 of
F0 and if I am taking 2 / 2 2 pi I Pi Pi
I which is equal to -1 into F of 1 then
how many steps it is needed it will need
only one one two and then here one
multiplication by one then addition 2
three uh three steps are needed so
here uh it is five and five is less than
definitely if I want to take n equal to
1 then this is this would be 8 so true
for n = 1
suppose true
for n = 2 ^ n minus of 1 then by
applying uh so cardinality of 2 ^ n by
LMA 2 into cardinality of 2 ^ N - of 1 +
8 into 2^ nus of 1 that is your M2 so
now this is equal to this is this is
what is true for this so this this is
less equal to 4 into 2 The Power here
this one is 4 into 2^ n
-1 into
2 uh
plus
uh into n n is this n
-1
plus uh this is
uh uh 8 m 8 into 2 ^ nus of 1
so this if we if we take this out then
uh this is 4 into 2 power n if I am
taking this out then I am going to get n
minus of 1 + 1 which is equal to 4 into
2^ n into n that is what so hence it is
true so by induction we can reduce
drastically if our n is of the form 2
The Power
uh uh n actually this kind of thing one
can do it suppose
remark if my n is some 3 to the^ n then
what I am going to do is that I will
take look at all the coets like uh 3K 3K
+ 1 3K + 2 and play the same game so in
that case what I am going to get is that
this is 6n log 3 to the base
n it's now if you go to for any natural
number K suppose n = to K the^ N then
what you are going to get is that 2
K uh
n then then this is uh uh log k b n that
is what so instead of n squ we are
bringing it down to in login that's a
real real good Improvement for the
computation and it must have made lot of
crystallographer uh very happy thank you
[Music]
[Music]
[Music]
