3. Divide & Conquer: FFT
Vložit
- čas přidán 3. 03. 2016
- MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: ocw.mit.edu/6-046JS15
Instructor: Erik Demaine
In this lecture, Professor Demaine continues with divide and conquer algorithms, introducing the fast fourier transform.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
Erik: "I didn't go to high school but I assume in high school you learned this..."
Students:"hahahaha"
convolution: 12:46
@@julius333333 and yet he’s such a humbling, sympathetic person
8:56
Weird flex but it hurts
Just a tip for new viewers:
Don't stop!! Continue watching the video, don't expect yourself to understand everything as you go, grab the essence of each section of the video and in the end it is all gonna make sense. If it did not you can always go back but don't quit this video. Amazing job Erik!!!
Thank you
This is very wise advise.
Thank you
I followed the strategy and now reading this comment. Going to advise the same
Am I the only one really impressed by the quality of that chalk? It never makes those high pitched sounds ... soo smooth
It's called railroad chalk. Made with calcium sulfate (gypsum), not calcium carbonate (chalk). Softer than chalk hence bolder lines and no screech. Dustier though, so treated with a dust inhibitor, that's why the surface of the stick is yellow but it writes in white.
I didnt want to watch this video because i hate that sound so much, thank you for the reassurance so i can watch without fear
Is it hagoromo?
@@vishalvibes_ nope
Not going to lie, I cam here to learn the FFT as an engineering student, but stuck around to learn about this CS time complexity.
same here haha
Kinda the whole point of the fft
The part about how size of X needs to be reduced by 2 when we go to X^2 is just brilliant! That explains the choice of x_k's that I saw on other ppl's implementation so well!
This is the best overview of what FFT is, brilliant teacher!
Professor makes his lecture seems the learning material is so easy! Thank you!
This is THE BEST FFT lecture ever. Erik is simply awesome!
Amazing to see that such a brilliant guy can also be a brilliant educator. From my experience this is pretty rare!
Its always a pleasure to listen Eric's lecture. Great professor.
I first encountered the FFT derivation of the DFT thirty years ago when I took a digital filters class while a graduate student at Georgia Tech, and I am as bolled-over now as I was then by this most elegant and incredibly useful algorithm. Thank you, Professor Demaine.
--
One of the best lectures I've seen :) really brings out the true nature of the DFT
27:46, we can use Lagrange's Formula to compute Coefficients from Samples. It is O(n^2) but avoids inverse computation by Gaussian Elimination.
This guy oozes brilliance! Amazing lecture!
As he puts it, this all was "very cool, very cool".
Thanks, Erik.
These tattoo jokes tho. BRILLIANT!
this lecture is freaking amazing
Gave an in depth understanding of FFT...Brilliant Explanation
Phenomenal lecture.
Real men cried at the end when he brought up those applications. Truly beautiful mathematics
My Brain Stack starts overflowing after 35:00.
Excellent explanation.
This was AWESOME! Thank you!
This guy is amazing
Didn't know that Jin from SamuraI Champloo now teaches at MIT.
Thanks for the amazing overview of FFT. Amazing lecture
lmaooo did not expect to see a samurai champloo reference while learning about the FFT
This is the most beautiful algorithm I have seen
wonderful teacher
Beware of the plot τwist.
Hidden spoilers
at last, absolute detail!
Throughout the whole video i could not stop wondering about him(he is a child prodigy, became a professor at MIT at 20 )
I don't know how I used to call myself an engineer before watching this video!
I loved this video.
Great Job!
So is the Nfft value for the FFT function in the matlab signal analyzer app the same as the 'n value rounded to the next largest power of 2' he talks about in the video?
Nicely explained
Erik, the best
This guy is so cool
Best lecture
Erik: "I didn't go to high school but I assume in high school you learned this..." reminds me seldon cooper
Amazing!
Sir what is the best programming language for analysis and design of data structures and algorithms??...
love it!!
Having barely mastered some basic arithmetic, this may be a little advanced...even though I have no idea wtf this guy is talking about/drawing, it is fascinating to try and understand it.
@@aristosgeorgiou6060 yeah, very relatable, lol
@@aristosgeorgiou6060 lol 🤣
@@aristosgeorgiou6060lol😂
Okay, we've figured out how to convert between different representations of polynomials, but how do we go from there to the familiar application of the FFT - converting between the time domain and frequency domain? Given a bunch of samples, we want a weighted sum of sinusoids, but what we get here is the coefficients of a polynomial.
This question has been plaguing me for a while. Did you ever discover an answer to this.
@@sophiophilethe coefficients that we get IS the FT, instead of the points being the coefficients of the polynomial representing the time domain function we get the samples from the polynomial representing the polynomial in frequency domain.
i was present in this class
That's a great thing. What are you doing now brother...?
Wow you went to mit? How did you apply, from India or USA?
I love you teacher
is there a mistake @28:35 ?
we know V.A = Y ( V - vandermond matrix, A - coefficien matrix, Y - samples matrix)
(multiplying by V inverse i.e. V^(-1) both sides)
=> V^(-1).V.A = V^(-1).Y
=> A = V^(-1).Y
So to go from samples matrix to coefficient matrix we need to do V^(-1).Y right ??
you are right.
it is a mistake
I think you are correct
Yes, this should be V^{-1} Y
the product of two n-1 degree polynomial will be 2n-2 and we need 2n-1 unique points to derive a 2n-2 degree polynomial and nth root of 1 gives just n points and not 2n So My question is dont we need 2n points intead of n?
It's already been noted that two polynomials should be reduced to the same degree and up to the nearest power of 2 (simply by adding the coefficients with zeros). In addition, as a result of the product of two polynomials of degree (n - 1) a polynomial of degree (2n - 2) is obtained; therefore, in order for the result to be correct, it is necessary to double the degrees of each polynomial (again by adding zero coefficients to them)
The tatoo gag is amazing!
Awesome!
High pass filter removes low frequency, and low pass filter removes high frequency
yeah, I caught this as well.
Marvellous
This was hard. Hope i will understand it soon.
Erik is Demaine man!
The root representation should be (x-r1)...(x-r(n-1)) not from (x-r0), you can easily see that if you do it from r0, then you will have polynomial of x^n (which is one degree higher than what he used in the first rep.)
He did this because he claimed you need n points to represent an n-1 polynomial. If you watch later into the video, he wrote it in this weird way cuz he was centring things around the number of points you need, not the number of coefficients represent the polynomial.
I like this guy
COOL! The only thing I don't prefer ( for lack of nicer word ) is the fact that he used a claim for last proof (IFFT). The problem with claims is that they are the result of some careful thinking, we're just proving that that thinking is correct. It would have been beautiful if he showed us the steps that resulted in the inverse of V being a n * V conjugate so we can fully sympathize for I believe sympathizing is the best way to learn math
Me: Has a school assignment where I have to implements an algorithm dividing two polynomials and I have no idea what to do
This man: I'm about to save this man whole career
Modify euclidean algorithm for gcd
How does one perform FFT on a larger domain consisting of multiple cosets of a multiplicative subgroup of the field? I've heard it can be done but couldn't find any sources that explained how.
*Stands up & claps* Eric, take a bow. This should be the reference for any instructor of how to explain the FFT.
in 42:06 I think we need to compute the sum of cost in each level not only the last !!!
Why do we still have x elements when we split the set and each part has n/2? I'm a bit confused on this part any help would be appreciated. Thanks.
44:00 in this moment, all the other stuff about fft made a little more sense :-)
Nice lecture! I thought MIT classes would be very hard.
MIT isn't a place for geniuses, it's just a normal university that only accepts students that can apply themselves.
I'm in third semester,but this particular video seems to much difficult ,there are so many things in this I don't know
Implemented FFT algo for both polynomial multiplication and integer multiplication
Deadly algo :)
% java FFTPolynomialMultiplication
i/p polynomial A :
2 + 3x + xˆ2
i/p polynomial B :
1 + 2xˆ2
n (=2ˆk) = 8
o/p polynomial C :
2 + 3x + 5xˆ2 + 6xˆ3 + 2xˆ4
% java FFTPolynomialMultiplication
i/p polynomial A :
8 + 7xˆ2 + 3xˆ3 + 9xˆ5
i/p polynomial B :
4 + 5x + 6xˆ2 + 7xˆ3 + 8xˆ4
n (=2ˆk) = 16
o/p polynomial C :
32 + 40x + 76xˆ2 + 103xˆ3 + 121xˆ4 + 103xˆ5 + 122xˆ6 + 78xˆ7 + 63xˆ8 + 72xˆ9
% java FFTIntegerMultiplication
i/p integers :
A = 123,456,789
B = 956,227,496
n = 32
product = 118,052,776,209,670,344
% java FFTIntegerMultiplication
i/p integers :
A = 2,147,483,647
B = 2,147,483,647
n = 32
product = 4,611,686,014,132,420,609
1:07:35 if the complex conjugate is just minus the power in the exponential, why did he write exp(-ijkT/n/n)? why the divide by n divide by n (again)? is it a mistake?
Because he's trying to invert the V-matrix which requires a complex conjugate operation and then a divide by n. Note he later corrected the division by n (because the magnitude of the xk values must be 1), and deferred it to after the matrix multiplication
I was just thinking earlier today about root 2/2 being the sine and cosine of 45 degrees, e^(2)i pi (e^i tau) and how they related to the unit square and circle. Fourier, Gauss, Dirichlet all stood on Euler's shoulders.
it always comes back to euler like it's rome
all roads, somewhere, somehow, all lead to euler
if there is a god, MIT is doing her work
So what is the math doing in practical terms? If I understand correctly, it's using the behavior of a signal over time to determine specific properties of that signal at specific moments. Is that correct?
The FFT has a lot of applications. What it's most usually associated with is frequency decomposition. The FFT is just a computationally faster way to calculate the discrete Fourier transform of a periodic signal, which extracts the frequency components of a signal. This is used for basically everything that deals with periodic signals.
More generally, the FFT can be expanded to include different roots of unity, like finite fields or integer integer rings, and that is used for cryptography and other various topics.
As far as practicality, this algorithm is a major step forward in the advancement of our species. It touches nearly everything in our current world.
Does anyone have intuition as to why Fourier transforms pop up here?
LOL 53:04 ^ 57:15 ^ 1:17:08
My only gripe is that an 80 minute video labeled Divide & Conquer FFT spends only 20 minutes discussing the FFT algorithm. Otherwise good.
This is what reaching GOD Level feels like in teaching?
I think he meant V\Y not V\A at around 29:00...
i think so too
Taylor's polynomial seems to be O(n) eval,addn and multiplication
is it just me or does he look like post malone had a studious brother
Erik: " I didn't go to high school, but I assume in high school algebra you learn this...."
Me: Drop from CS and cry...
Pro Erik is fabulous
Did he just throw a Frisbee at 4:54 ? I cracked up xD
I guess the idea is to somehow encourage participation. I'd like to know if there's a more in-depth study about this - does it enhance or take away concentration from the actual subject? (Or choice C - neither, it's just a bit of fun)
let me know if u ever found an answer to it @orbik.
sounds a little like dog training where you throw a frisbee as a reward for the dog.
czcams.com/video/HtSuA80QTyo/video.html Here you go watch at 26:27 in that video, Instructor: Srini Devadas, mentions about it!
55:13 This should be squared no?
holy crap, the tau thing
why we must take the nth root of unity, cant we take like -1, 1, -2, 2 ....as X? This will also collapse?
Squaring those numbers will give you 1, 1, 4, 4, giving you the set {1, 4} (a collapse of 4 numbers to 2), but if you square those again you get {1, 16}, which doesn't collapse the set any further. You need the collapsed set to collapse again when you square each value a second time, and then collapse again when you square the numbers a third time, and so on, hence the complex numbers. You could use the nth roots of any number, but using the nth roots of 1 is simpler and lends the alternative representation to represent amplitude and phase information in frequency space. If you used the nth roots of another number I don’t think the alternative representation could be interpreted the same way.
@@elliotwaite 1:07:35 if the complex conjugate is just minus the power in the exponential, why did he write exp(-ijkT/n/n)? why the divide by n divide by n (again)? is it a mistake?
(also sorry I asked as subcomment; I thought it'd get lost in the clutter otherwise)
@@haardshah1676 it looks like the second division by n was a mistake. He realizes this soon after writing it and erases it. Does that answer your question?
"Screw Pi" - omg i nearly died. That was hilarious. I deeply regret my decision to avoid STEM classes in high school and college. That was a terrible mistake.
It’s not too late to learn. Think of the ones you regret not taking and either purchase a book or take a class. One of the greatest things about our minds is that they are malleable.
FFT sounds like fast Fourier transformation I don’t know what it is though
Let me guess, it involves powers of 2?
whats the deal with those frizbees?
Is it too complex or just a first impression?
Is divide and conquer a genetic algorithm?
53:07 "I believe in Tau so much, I got it tattooed on my arm..."
wow,lollllllllllll
is there a followup to this lecture?
Here's the recitation that followed the lecture. Linking to it from the playlist: czcams.com/video/TOb1tuEZ2X4/video.html&pp=iAQB. We hope this is what you are looking for.
Can someone explain why at 40:16 the last item is O(n + |x|)? Where does this n come from? I think it should be O(|X|) because once we get Aeven(x) and Aodd(x) for any x in X, it just constant time to compute Aeven(x) + x*Aodd(x) for each x. Now we have |X| points to computer, so it takes |X| time to get A(x) for x in X. Correct me if I am wrong
This is a very late comment but I'm posting so that other people can see. I think that n comes from creating the two coefficient vectors for the two polynomials A_even and A_odd by linearly scanning the coefficient vector of the polynomial A.
9:54 can anybody why it is O(n^2) ?
nvm, i was dumb. it was n term times n terms so it should be n^2
Dude, why are you erasing the chalkboard before I finish taking notes?
In what minute did you get lost?
last lecture, actually
just wandering around from there
well I actually got lost in 6.006
TAU IS A WHOLE CIRCLE
Did I come here planning to learn about the nth roots of unity and how polynomial representations can be exploited to improve the scaling of computational complexity... No
Did I just spend an hour watching this guy because it is freaking interesting and incredibly well presented? You bet I did 😅
How can i find the full playlist?
Every MIT OpenCourseWare course on CZcams has a playlist. They are named by the course. In this case, the playlist is "MIT 6.046J Design and Analysis of Algorithms, Spring 2015" czcams.com/play/PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp.html. Every video we publish has the course name and number in the video description. Best wishes on your studies!
OMG why is this not the standard way of introducing FFT
I think there is one mistake at 15:36, when he wrote down samples to represent a polynomial of degree n. He took n samples to represent a polynomial of degree n uniquely. But this is untrue, to represent a polynomial of degree n, we need at least n+1 sample points, for all different x points.
The polynomial is of degree n-1: (1 + x + ... + x^(n-1)). Therefore, you need n sample points to uniquely represent this polynomial.