The Fast Fourier Transform Algorithm

Поделиться
HTML-код
  • Опубликовано: 25 авг 2024
  • 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/...
    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...
    Brunton Website: eigensteve.com
    This video was produced at the University of Washington

Комментарии • 95

  • @HuyNguyen-fp7oz
    @HuyNguyen-fp7oz 3 года назад +44

    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
    @hoodoooperator.5197 2 года назад +14

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

  • @torgeirHD03
    @torgeirHD03 9 месяцев назад +4

    Such an elegant method using divide and conquer :)

  • @ripsirwin1
    @ripsirwin1 11 месяцев назад +3

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

  • @saitaro
    @saitaro 4 года назад +15

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

  • @ZetaCarinae
    @ZetaCarinae 4 года назад +65

    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
      @Eigensteve  4 года назад +41

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

    • @videofountain
      @videofountain 4 года назад +2

      @mathIsART pasta?

    • @ABHISHEKSINGH-nv1se
      @ABHISHEKSINGH-nv1se 3 года назад

      i was going to comment for this.

    • @edmason7346
      @edmason7346 3 года назад +2

      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
      @user-nk4bj9gb4e 2 месяца назад

      ah, thanks

  • @TechnologySandBOX
    @TechnologySandBOX 3 года назад +9

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

  • @toastom
    @toastom 2 года назад +1

    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.

  • @aakashdewangan7313
    @aakashdewangan7313 2 года назад

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

  • @nkminwings
    @nkminwings 4 года назад +8

    Great lecture! Understand clearly. Thanks👍

  • @macroxela
    @macroxela 5 месяцев назад

    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.

  • @RenzymEducation
    @RenzymEducation 2 года назад +2

    For those who want to go a little bit further in details and watch Gilbert Strang's lecture, here it is:
    ruclips.net/video/M0Sa8fLOajA/видео.html

  • @fdmeneses
    @fdmeneses 4 года назад +4

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

  • @RobotLabX
    @RobotLabX 3 года назад +4

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

  • @Damocles1337
    @Damocles1337 3 года назад +30

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

    • @ewout256
      @ewout256 3 года назад +18

      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
      @christopherjoseph651 3 года назад +5

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

    • @lachlanpage7819
      @lachlanpage7819 3 года назад +7

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

    • @angelodeluca2839
      @angelodeluca2839 3 года назад +8

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

    • @michaeltamajong2988
      @michaeltamajong2988 9 месяцев назад

      In addition, looks like he is left handed 😊

  • @zokalyx
    @zokalyx Год назад +3

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

  • @SohamChakraborty42069
    @SohamChakraborty42069 9 месяцев назад

    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

  • @roozbehehsani1468
    @roozbehehsani1468 2 года назад

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

  • @IsusaWH
    @IsusaWH 4 года назад +1

    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.

  • @sathviknallapuri4667
    @sathviknallapuri4667 2 года назад

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

  • @aliasgeranees8893
    @aliasgeranees8893 4 года назад +5

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

    • @Eigensteve
      @Eigensteve  4 года назад +12

      I was thinking about ruclips.net/video/M0Sa8fLOajA/видео.html and ocw.mit.edu/courses/mathematics/18-085-computational-science-and-engineering-i-fall-2008/video-lectures/lecture-31-fast-fourier-transform-convolution/

  • @rafbi4874
    @rafbi4874 Год назад

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

  • @ehabnasr6925
    @ehabnasr6925 2 года назад +4

    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?

  • @dipanjanmech
    @dipanjanmech 3 года назад +1

    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.

  • @mohd12453
    @mohd12453 4 года назад +3

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

  • @osamamamabutam7934
    @osamamamabutam7934 2 года назад

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

  • @mu.makbarzadeh2831
    @mu.makbarzadeh2831 4 года назад +5

    A googleplus of thanks🌹🌹🌹

  • @videofountain
    @videofountain 2 месяца назад

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

  • @AmbiguousAdventurer
    @AmbiguousAdventurer 3 года назад

    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

  • @naaz7991
    @naaz7991 3 года назад

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

  • @AJ-et3vf
    @AJ-et3vf Год назад

    Awesome video. Thank you

  • @albertodedavide3971
    @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

  • @thelifeofahuman3666
    @thelifeofahuman3666 3 года назад

    Amazing explanation sir

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

  • @epicmorphism2240
    @epicmorphism2240 4 года назад +2

    Thank you!

  • @erickappel4120
    @erickappel4120 3 месяца назад

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

  • @ElMalikHydaspes
    @ElMalikHydaspes 6 месяцев назад

    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: ruclips.net/video/M0Sa8fLOajA/видео.html

  • @saisharath4721
    @saisharath4721 4 года назад +1

    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?

  • @shaikon5617
    @shaikon5617 3 года назад

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

  • @usefulandentertainingd3836
    @usefulandentertainingd3836 3 года назад

    Very good content

  • @subratadutta7710
    @subratadutta7710 Год назад

    Great!!!!

  • @berkayeryldz2059
    @berkayeryldz2059 2 года назад

    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.

  • @neerajcheryala9602
    @neerajcheryala9602 4 года назад +4

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

    • @Eigensteve
      @Eigensteve  4 года назад +5

      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
      @neerajcheryala9602 4 года назад

      @@Eigensteve Thank you sir

    • @wuxi8773
      @wuxi8773 4 года назад +1

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

  • @PedramNG
    @PedramNG 3 года назад +1

    Amazing.

  • @qje2643
    @qje2643 4 года назад

    very clear, thank you

  • @hoaxuan7074
    @hoaxuan7074 3 года назад

    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.

  • @angelodeluca2839
    @angelodeluca2839 3 года назад

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

  • @TheMechatronicEngineer
    @TheMechatronicEngineer Год назад

    Amazing!

  • @RESEARCH100500
    @RESEARCH100500 3 месяца назад

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

  • @alicewonderland9151
    @alicewonderland9151 2 года назад

    It's legendary!

  • @EEMendel
    @EEMendel Год назад

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

  • @mattswanson557
    @mattswanson557 2 года назад

    How are you writing backwards??

  • @user-hr3qh5dt7n
    @user-hr3qh5dt7n 9 месяцев назад

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

  • @user-vv8mo6fj3n
    @user-vv8mo6fj3n Год назад

    Why Transform not found.. I dont understan english language

  • @varijpatelz
    @varijpatelz 3 года назад

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

  • @taxessux
    @taxessux 4 года назад +1

    do a video on how you write backwards

    • @infinitydude7305
      @infinitydude7305 4 года назад +1

      seriously, how does he do that?

    • @abhinandande8805
      @abhinandande8805 4 года назад +3

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

  • @Weezyme007
    @Weezyme007 4 года назад

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

    • @sharanyar1236
      @sharanyar1236 3 года назад +3

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

  • @sudhamani5149
    @sudhamani5149 4 года назад +1

    How are you writing like that?

    • @srijanraghunath4642
      @srijanraghunath4642 4 года назад +1

      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
      @andreasalati3591 3 года назад

      @@srijanraghunath4642 so is he left handed than?

    • @srijanraghunath4642
      @srijanraghunath4642 3 года назад

      @@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
      @brianmcmullen95 3 года назад

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

  • @shaaoux5590
    @shaaoux5590 Год назад

    wait, does this lecturer write everything in reverse?

    • @shaaoux5590
      @shaaoux5590 Год назад

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

  • @dlbattle100
    @dlbattle100 2 года назад

    0,2,4,6; not 8

  • @johnwt7333
    @johnwt7333 3 года назад

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

  • @vasilijeivanovic931
    @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

  • @dobotube
    @dobotube 2 года назад

    The 6th element of the vector is very sad 😢

  • @mathematician849
    @mathematician849 2 года назад

    This factorization was never taught to us

  • @guranshsingh3215
    @guranshsingh3215 2 года назад

    forgot about 6

  • @Tushar-pg2em
    @Tushar-pg2em Год назад

    Sir u missed 6...😂😂

  • @johnyoungquist6540
    @johnyoungquist6540 4 года назад +1

    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
    @christopherjoseph651 3 года назад +1

    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
    @Tristoo 3 года назад

    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!