The Fast Fourier Transform Algorithm

Here I discuss the Fast Fourier Transform (FFT) algorithm, one of the most important algorithms of all time.
Book Website: databookuw.com
Book PDF: databookuw.com/databook.pdf
These lectures follow Chapter 2 from:
"Data-Driven Science and Engineering: Machine Learning, Dynamical Systems, and Control" by Brunton and Kutz
Amazon: www.amazon.com/Data-Driven-Sc...
Brunton Website: eigensteve.com
This video was produced at the University of Washington

[@HuyNguyen-fp7oz]

I recommend your channel to my friends when they asked me to explain how FFT works. Great channel!!!!! Keep up the good work professor!!!

[@hoodoooperator.5197]

Steve, I've just paraphrased (and sourced) this video in my final report for my MSc project. “The FFT is based on the fundamental observation that the DFT matrix has so much symmetry that if the even and odd indices are reordered, one can massively simplify the calculation by taking advantage of redundancies and cutting the DFT computation in half, recursively”.

[@RobotLabX]

Thank you for sharing, Steve Brunton. This is great lecture!

[@fdmeneses]

beautiful lectures that inspire a desire to learn. Your work is much appreciated, thanks!

[@torgeirHD03]

Such an elegant method using divide and conquer :)

[@nkminwings]

Great lecture! Understand clearly. Thanks👍

[@roozbehehsani1468]

I can confidently say that this is a great channel. I liked every video. Many Thanks.

[@ripsirwin1]

I also recommend reading "Numerical Recipes" in C or Fortran, it explains this algorithm from a computer scientist's perspective.

[@saitaro]

A notion of prof. Strang is always a good sign.

[@naaz7991]

Thank you so much Steve. Cleared the concept. :)

[@RenzymEducation]

For those who want to go a little bit further in details and watch Gilbert Strang's lecture, here it is: kzbin.info/www/bejne/g2G2kmucgbSUoKM

[@sathviknallapuri4667]

Simply Wow!! I truly enjoyed watching this entire video and its like, u made me get inspired. Thank you for this awesome lecture.

[@ZetaCarinae]

Your central matrix factorization is not quite right. The top two blocks should be [I_{512}, D_{512}] instead of [I_{512}, -D_{512}] . Looks like the same error is in your databook.pdf.

[@Eigensteve]

Great catch! The upper right matrix should be D_{512} instead of D_{-512}. Thanks for catching this!

[@videofountain]

@mathIsART pasta?

[@ABHISHEKSINGH-nv1se]

i was going to comment for this.

[@edmason7346]

The fact that that occurred to me while watching, and then came down here to confirm, must mean that I'm beginning to actually comprehend this stuff!

[@user-nk4bj9gb4e]

ah, thanks

[@osamamamabutam7934]

thanks you.... you helped me a lot. your work is appreciated

[@aakashdewangan7313]

first time in my life I have seen the clear working of FFT. WoW..........Awesome

[@thelifeofahuman3666]

Amazing explanation sir

[@ehabnasr6925]

Amazing Lectures! Thank you very much! I have a question: In terms of threading and parallelization (like with OpenMP or CUDA) do you think the FFT is better? I'm just thinking; because it seems that even DFT has a higher order of computation FFT seems to have a longer span/critical path of computation.. meaning more bottlenecks/parallelization inhibitors?

[@AJ-et3vf]

Awesome video. Thank you

[@TechnologySandBOX]

Very informative lecture, learned a lot from it. However, at 6:50, the even indexes must 0,2,4,(6 NOT 8).

[@mohd12453]

@alpha_grand has invited me to watch it. Very interesting topic mate. Cheers,

[@qje2643]

very clear, thank you

[@saisharath4721]

Great explanation! Thanks. One question though, could you please tell, which matrix contains the rest of the powers of 'w' i.e. from 512 to 1023?

[@toastom]

Hate to say it, but my signal processing class is nothing like this. My professor only goes over the math parts and nothing more. He doesn't even mention how any of it is used to process signals. So thank you for actually putting the SIGNAL in SIGNAL PROCESSING.

[@epicmorphism2240]

Thank you!

[@angelodeluca2839]

Fantastic overview! Sorry if this is a dumb question-but what do the "diagonal" matrices contain?

[@usefulandentertainingd3836]

Very good content

[@aliasgeranees8893]

Awesome video sir...can u please give the link to that mit lecture u were talking about

[@Eigensteve]

I was thinking about kzbin.info/www/bejne/g2G2kmucgbSUoKM and ocw.mit.edu/courses/mathematics/18-085-computational-science-and-engineering-i-fall-2008/video-lectures/lecture-31-fast-fourier-transform-convolution/

[@TheMechatronicEngineer]

Amazing!

[@dipanjanmech]

Thanks for the great lecture. Just one very minor thing. At 04.52 you said 1012 by 1012 matrix, I think it will be 1024 by 1024.

[@SohamChakraborty42069]

Visitng your lectures for my Bachelor's Thesis Project! I think there are very few teachers who are as coherent as you! 8th November, 2023. 1:15 AM

[@mu.makbarzadeh2831]

A googleplus of thanks🌹🌹🌹

[@Damocles1337]

did anyone else realize how well this guy can write backwards?

[@ewout256]

The image is just mirrored. He writes normally, if you were to see the actual back of the board it would be mirrored so they just flipped the image again after recording. He is actually left handed (note his wedding ring as well, on his actual left hand) and his hair lies to the other side in real life.

[@christopherjoseph651]

Did anyone else realize how stupid all the people are that think he's writing backwards

[@lachlanpage7819]

@@christopherjoseph651 Did you realize you don't have to be rude?

[@angelodeluca2839]

@@ewout256 Plot twist: the image isn't mirrored; he has godlike writing abilities.

[@michaeltamajong2988]

In addition, looks like he is left handed 😊

[@AmbiguousAdventurer]

I'm trying to get an intuitive understanding of FFT algorithm...can we say it's a play on the exponent by repeated squaring algorithm. It basically optimized by reducing repeated calculation of Wn^k. Or from another angle it is dynamic programming where the common building blocks Wn^k

[@rafbi4874]

ARE YOU WRITING IN REVERSE!? THAT'S AMAZING!

[@alicewonderland9151]

It's legendary!

[@berkayeryldz2059]

Hello professor, I am recently writing my thesis in experimental aerodynamics area and watching your videos to learn the signal processing techniques. Your videos are the most beneficial academic videos I have ever watched. But I have to cite the information on the videos. How should I do that? Thanks in advance, respects.

[@IsusaWH]

Dear Steve, using text to speech api's and auto sync tools I have created English subtitles for this video. Please let me know if you want me to send them to you. They aren't perfect, but they are useful.

[@macroxela]

0:32 this video series has been wonderful but I believe that the ball was dropped here. In the previous section, the DFT algorithm was shown for the exact same reasons the FFT algorithm wasn't shown here. The DFT videos are excellent because they combined code with a brief overview. Simply showing the code, even if briefly, would help a lot with better understanding how the FFT works. Yes, it is a standard algorithm but because it is so, most instructors say the exact same thing so they don't have to explain it which makes it difficult to find a good explanation using code.

[@PedramNG]

Amazing.

[@Eigensteve]

Thanks!

[@subratadutta7710]

Great!!!!

[@hoaxuan7074]

It's interesting the FFT has too many dimensions for each dot product to be orthogonal. Obviously at each frequency the 2 dot products (sine and cosine) are orthogonal. The Hadamard transform is a much simpler case.

[@zokalyx]

Shouldn't the matrix be: [ I +D ] [ I -D ] @3:52

[@o_2731]

The DFT matrix has to be calculated anyway right? So this FFT is just used to speed up the multiplication of the input vector with the DFT matrix?

[@videofountain]

At the time 6:59 is written the even numbers [0248]. Did you intend to write [0246]?

[@Weezyme007]

Around 7:00 I didnt really understand how does the second time even and odd arrangement works? Please let me know! Thanks.

[@sharanyar1236]

This is what i've understood - 1 and 5 leave remainders of 1 (mod 4) while 3 and 7 leave remainders of 3 (mod 4). the groups are 0,4 (=0 mod 4), 2,6(=2 mod 4) 1,5(=1 mod 4) and 3,7(=3 mod 4). The next step would have all numbers grouped by remainders mod 8

[@charlesmrader]

Dr. Brunton has some habits of mixing up indexing starting with 0 and indexing starting with 1. If you consistently use indexing from 0, the evens would be 0,2,4,6 and the odds would be 1,3,5,7 but starting with 1, the sets would be 1,3,5,7 and 0,2,4,6. In his example at about seven minutes he shows sets 0,2,4,8 and 1,3,5,7, which is really wrong, but just because of that indexing inconsistency.

[@albertodedavide3971]

that's what i needed. However i would prefer to hear you talking about what you do than the music. Still very comprensibile btw

[@neerajcheryala9602]

Sir, where can I get the C code for FFT?

[@Eigensteve]

I am not 100% sure, but I seem to remember this being in the "Numerical Recipes in C" book. If you google this, I think you'll find it.

[@neerajcheryala9602]

@@Eigensteve Thank you sir

[@wuxi8773]

@@neerajcheryala9602 if you really want, I can write one for you from scratch.

[@varijpatelz]

Hi, so [ F 0; 0 F] is nothing but diagonal entries of the fk-even and fk-odd coefficient after bitwise shuffling.

[@erickappel4120]

Steve, ... You missed the f6 term in the first FFT split.

[@shaikon5617]

When such content is concerned - KZbin really shouldn't limit users to just one LIKE per video. Should be at least 1024...

[@taxessux]

do a video on how you write backwards

[@infinitydude7305]

seriously, how does he do that?

[@abhinandande8805]

@@infinitydude7305 He writes forward and simply mirrors the screen :)

[@mattswanson557]

How are you writing backwards??

[@ElMalikHydaspes]

Dr Brunton mentioned Strand ... For those wanting to see Dr Gilbert Strand's 'in-depth' lecture that goes [elegantly & simply] into the bit more math of the construction of the FFT via the Fourier matrix, here is a good lecture: kzbin.info/www/bejne/g2G2kmucgbSUoKM

[@user-hr3qh5dt7n]

Before I understand FFT, I want to understand how he's writing mirrored so effortlessly.

[@EEMendel]

The only thing I can't wrap my head around is how he is writing everything backwards.

[@RESEARCH100500]

1st part was really good. Yhis part looks like "how to draw an owl"

[@sudhamani5149]

How are you writing like that?

[@srijanraghunath4642]

if ur talking about how hes writing in reverse, hes not. He simply writes normally so that the camera picks up the writings in reverse. He then reverse or mirror-images the video so anything thats in reverse is normal.

[@andreasalati3591]

@@srijanraghunath4642 so is he left handed than?

[@srijanraghunath4642]

@@andreasalati3591 Probably im just guessing he does this because it would be insane if he wrote stuff in reverse all the time when he could resort to much simpler things like i mentioned

[@brianmcmullen95]

@@andreasalati3591 Yep. Much more likely than putting in the effort to learn to write backwards perfectly.

[@johnwt7333]

Sir, your explanations are excellent. Although a bit too convoluted at some points.

[@user-vv8mo6fj3n]

Why Transform not found.. I dont understan english language

[@shaaoux5590]

wait, does this lecturer write everything in reverse?

[@shaaoux5590]

I got it. this one must have a heart on the right😂

[@dlbattle100]

0,2,4,6; not 8

[@dobotube]

The 6th element of the vector is very sad 😢

[@vasilijeivanovic931]

This is really an engineering video. It doesn't use or show why something is true in theory, but just shows how it works, not WHY it works

[@mathematician849]

This factorization was never taught to us

[@guranshsingh3215]

forgot about 6

[@Tushar-pg2em]

Sir u missed 6...😂😂

[@johnyoungquist6540]

I watched Strangs lecture 31 on FFT. I don't know if this is the one you referred to. He is a confused mess. . I don't think he understands how the FFT actually works and is certain incapable of explaining it..

[@christopherjoseph651]

COMPLETELY USELESS! Here's a video on the FFT algorithm but I'm not actually going to show you the algorithm because you're not going to code it up

[@Tristoo]

Bro you make some very good videos but I gotta be honest your swallowing tick thing gives me anxiety to the point I wanna punch the screen every time you do it. Also maybe some examples, even with tiny matrices would have helped me a lot as that way I could just look at the screen to get it instead of going back like 5 times to re-hear what you said until I do. Hopefully you can appreciate my dumb observations, thank you!