3. Divide & Conquer: FFT

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

[@junweima]

Erik: "I didn't go to high school but I assume in high school you learned this..."

[@rj-nj3uk]

Students:"hahahaha"

[@godfather5557]

convolution: 12:46

[@m322_yt]

@@julius333333 and yet he’s such a humbling, sympathetic person

[@tsunghan_yu]

8:56

[@hemiacetal1331]

Weird flex but it hurts

[@KaushikMishrakk]

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!!!

[@chill6962]

Thank you

[@migueld2456]

This is very wise advise.

[@__dekana__]

Thank you

[@user-cc4pq9cd3r]

I followed the strategy and now reading this comment. Going to advise the same

[@andrestifyable]

Am I the only one really impressed by the quality of that chalk? It never makes those high pitched sounds ... soo smooth

[@hektor6766]

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.

[@matthewquinn5192]

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

[@vishalvibes_]

Is it hagoromo?

[@henrypeterson8497]

@@vishalvibes_ nope

[@TW0T0NGUE]

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.

[@tennma6250]

same here haha

[@woosix7735]

Kinda the whole point of the fft

[@abdulelahaljeffery6234]

This is the best overview of what FFT is, brilliant teacher!

[@leminhphuc10t1]

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!

[@personanongrata987]

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. --

[@yashjakhotiya5808]

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.

[@mario7501]

Amazing to see that such a brilliant guy can also be a brilliant educator. From my experience this is pretty rare!

[@nayuki2020]

around 1:20:00, you can't get pure sine wave from striking a bell. Bell, or piano, or a person singing the same note each has a unique timbre to it. Use an online sine wave generator and listen to what a pure tone sounds like (at a certain frequency). Sing that out feel the difference, and view it under a frequency analyzer, they will look vastly different.

[@tibortresla]

These tattoo jokes tho. BRILLIANT!

[@henrytay1706]

Professor makes his lecture seems the learning material is so easy! Thank you!

[@skyzhangty1]

This is THE BEST FFT lecture ever. Erik is simply awesome!

[@akshaydarekar5863]

My Brain Stack starts overflowing after 35:00.

[@nalcow]

Its always a pleasure to listen Eric's lecture. Great professor.

[@randomperson1048]

Real men cried at the end when he brought up those applications. Truly beautiful mathematics

[@aSeaofTroubles]

One of the best lectures I've seen :) really brings out the true nature of the DFT

[@sanatanshrivastava1725]

As he puts it, this all was "very cool, very cool". Thanks, Erik.

[@szyszkienty]

This guy oozes brilliance! Amazing lecture!

[@DominicLondon]

Beware of the plot τwist.

[@vishalvibes_]

Hidden spoilers

[@vamsimohan5369]

Throughout the whole video i could not stop wondering about him(he is a child prodigy, became a professor at MIT at 20 )

[@programmingbro2424]

this lecture is freaking amazing

[@muhammedafifi6388]

I don't know how I used to call myself an engineer before watching this video!

[@chethankumar4303]

Gave an in depth understanding of FFT...Brilliant Explanation

[@Kaslor1000]

Phenomenal lecture.

[@mavenuparker]

Didn't know that Jin from SamuraI Champloo now teaches at MIT. Thanks for the amazing overview of FFT. Amazing lecture

[@SR-kp8zu]

lmaooo did not expect to see a samurai champloo reference while learning about the FFT

[@jayhoeliotdecabrio4050]

Erik: "I didn't go to high school but I assume in high school you learned this..." reminds me seldon cooper

[@nikhil_kolla_12]

Excellent explanation.

[@stefanosmakris5641]

This was AWESOME! Thank you!

[@sakules]

wonderful teacher

[@sa6opopov]

This is the most beautiful algorithm I have seen

[@paragggoyal1552]

at last, absolute detail!

[@RSPSupply]

Great Job!

[@iamshadmirza]

This guy is amazing

[@andrewolesen8773]

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?

[@fatihcihanhizlikan1427]

I loved this video.

[@shivamtomar2325]

Nicely explained

[@leeris19]

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

[@rohankhandelwal7681]

i was present in this class

[@Deshammanideep]

That's a great thing. What are you doing now brother...?

[@vetiarvind]

Wow you went to mit? How did you apply, from India or USA?

[@RandomGuy12562]

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 ??

[@donxu1332]

you are right. it is a mistake

[@danielf9110]

I think you are correct

[@AdamCajf]

Yes, this should be V^{-1} Y

[@suicide_king6804]

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.

[@BenjaminKorenBJK]

@@aristosgeorgiou6060 yeah, very relatable, lol

[@karanveersingh5535]

@@aristosgeorgiou6060 lol 🤣

[@saicharanmarrivada5077]

@@aristosgeorgiou6060lol😂

[@c0t556]

This guy is so cool

[@domenicozaza192]

The tatoo gag is amazing!

[@udomatthiasdrums5322]

love it!!

[@MaxMarrone]

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.

[@sophiophile]

This question has been plaguing me for a while. Did you ever discover an answer to this.

[@THeMin1000]

@@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.

[@beback_]

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.

[@everaldoantoniomoreiraalve1023]

Amazing!

[@BuiDucLoc419]

Best lecture

[@kaiovieira230]

Awesome!

[@madhukiranattivilli2321]

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

[@chinmaydas4053]

Sir what is the best programming language for analysis and design of data structures and algorithms??...

[@kaustavguharoy4532]

Marvellous

[@khoily9137]

High pass filter removes low frequency, and low pass filter removes high frequency

[@xinli6243]

yeah, I caught this as well.

[@linuxmaster2327]

I love you teacher

[@prateeksamaiya]

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?

[@_rashadmammadov_]

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)

[@martinstefcek4089]

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.)

[@sophiophile]

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.

[@shivamp5410]

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.

[@Selbstzensur]

This was hard. Hope i will understand it soon.

[@woosix7735]

I like this guy

[@azizchafik]

in 42:06 I think we need to compute the sum of cost in each level not only the last !!!

[@saltcheese]

if there is a god, MIT is doing her work

[@kaushiksurikuchi]

Erik, the best

[@abugigi]

Erik is Demaine man!

[@noguide]

*Stands up & claps* Eric, take a bow. This should be the reference for any instructor of how to explain the FFT.

[@TheBoutchard]

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

[@bhaskarpandey8586]

Modify euclidean algorithm for gcd

[@Selbstzensur]

44:00 in this moment, all the other stuff about fft made a little more sense :-)

[@BigBHole69]

My only gripe is that an 80 minute video labeled Divide & Conquer FFT spends only 20 minutes discussing the FFT algorithm. Otherwise good.

[@roushankumar-lu2ov]

I'm in third semester,but this particular video seems to much difficult ,there are so many things in this I don't know

[@AmanGarg95]

Did he just throw a Frisbee at 4:54 ? I cracked up xD

[@orbik_fin]

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)

[@GMPGIRI]

let me know if u ever found an answer to it @orbik.

[@TheKivifreak]

sounds a little like dog training where you throw a frisbee as a reward for the dog.

[@ashishjog]

kzbin.info/www/bejne/fqW2pnRuZbaHr9E Here you go watch at 26:27 in that video, Instructor: Srini Devadas, mentions about it!

[@haardshah1676]

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?

[@willlenk862]

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

[@not_melkor]

This is what reaching GOD Level feels like in teaching?

[@MrAwesomeaditya]

is it just me or does he look like post malone had a studious brother

[@phillipabramson9610]

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?

[@chrism7574]

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.

[@noguide]

LOL 53:04 ^ 57:15 ^ 1:17:08

[@vivekdabholkar5965]

Nice lecture! I thought MIT classes would be very hard.

[@BTDiLmarinen]

MIT isn't a place for geniuses, it's just a normal university that only accepts students that can apply themselves.

[@thinhnguyenvan7003]

53:07 "I believe in Tau so much, I got it tattooed on my arm..." wow,lollllllllllll

[@64standardtrickyness]

Does anyone have intuition as to why Fourier transforms pop up here?

[@erans0496]

Erik: " I didn't go to high school, but I assume in high school algebra you learn this...." Me: Drop from CS and cry...

[@hektor6766]

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.

[@englishmotherfucker1058]

it always comes back to euler like it's rome all roads, somewhere, somehow, all lead to euler

[@aayushbajaj2260]

holy crap, the tau thing

[@93nites]

Taylor's polynomial seems to be O(n) eval,addn and multiplication

[@off4on]

I think he meant V\Y not V\A at around 29:00...

[@junzhai1715]

i think so too

[@paragggoyal1552]

you look so excited just wait till i hit you, you will be less excited. LOL at 15:40

[@kokomanation]

FFT sounds like fast Fourier transformation I don’t know what it is though

[@distrologic2925]

TAU IS A WHOLE CIRCLE

[@ilyboc]

55:13 This should be squared no?

[@wtw5002]

"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.

[@ka1wht]

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.

[@rosenzhang1704]

why we must take the nth root of unity, cant we take like -1, 1, -2, 2 ....as X? This will also collapse?

[@elliotwaite]

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.

[@haardshah1676]

​@@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)

[@elliotwaite]

@@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?

[@rodacoram]

Is divide and conquer a genetic algorithm?

[@Harish-ou4dy]

whats the deal with those frizbees?

[@5daydreams]

is there a followup to this lecture?

[@mitocw]

Here's the recitation that followed the lecture. Linking to it from the playlist: kzbin.info/www/bejne/ioDFYqerer9ljpY&pp=iAQB. We hope this is what you are looking for.

[@bryanlozano8905]

Dude, why are you erasing the chalkboard before I finish taking notes?

[@HeisenbergHK]

How can i find the full playlist?

[@mitocw]

Every MIT OpenCourseWare course on KZbin 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" kzbin.info/aero/PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp. Every video we publish has the course name and number in the video description. Best wishes on your studies!

[@64standardtrickyness]

OMG why is this not the standard way of introducing FFT

[@xinli6243]

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

[@kyawshinthant4237]

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.

[@ezzoalgaddafy5934]

Is it too complex or just a first impression?

[@qiguosun129]

Pro Erik is fabulous

[@pepehimovic3135]

Let me guess, it involves powers of 2?

[@LydellAaron]

53:06, 57:15 takes a moment to give tau some respect. Big flex 💪

[@DarwinsBuddy]

cool! free frisbees@MIT