The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?
In this video, we take a look at one of the most beautiful algorithms ever created: the Fast Fourier Transform (FFT). This is a tricky algorithm to understand so we take a look at it in a context that we are all familiar with: polynomial multiplication. You will see how the core ideas of the FFT can be "discovered" through asking the right questions. The key insights that are presented in this video is that polynomial multiplication can be improved significantly by multiplying polynomials in a special value representation. The challenge that presents itself is the problem of converting a polynomial from a standard coefficient representation to value representation.
We see that the FFT is an incredibly efficient recursive algorithm that performs this task, and we also discover that a slightly tweaked FFT (Inverse FFT) can also solve the reverse problem of interpolation. If this video doesn't blow your mind, I don't know what will.
0:00 Introduction
2:19 Polynomial Multiplication
3:36 Polynomial Representation
6:06 Value Representation Advantages
7:07 Polynomial Multiplication Flowchart
8:04 Polynomial Evaluation
13:49 Which Evaluation Points?
16:30 Why Nth Roots of Unity?
18:28 FFT Implementation
22:47 Interpolation and Inverse FFT
26:49 Recap
Also a subtle mistake that a commenter made me aware of -- at 26:40 instead of replacing w with (1/n * e^{-2 * pi i/ n}), the actual right way to do this is by taking the final output of the IFFT at the end of the recursion and dividing by n.
So the full change is w = e^{-2 pi i / n}
And then somewhere outside the scope of the IFFT function ifft_result = 1/n * IFFT(values)
The treatment of the FFT in this video is inspired by several well known references, mainly Introduction to Algorithms (Cormen et al.) and Algorithms (Papadimitriou et al.).
Support: https://www.patreon.com/reducible
This video wouldn't be possible without the open source manim library created by 3blue1brown: https://github.com/3b1b/manim
Here is link to the repository that contains the code used to generate the animations in this video: https://github.com/nipunramk/Reducible
Elegant proof that the matrix used in the proof that (d + 1) points uniquely define a degree d polynomial is invertible: https://math.stackexchange.com/questions/426932/why-are-vandermonde-matrices-invertible
Music:
Lift Motif by Kevin MacLeod is licensed under a Creative Commons Attribution license (https://creativecommons.org/licenses/...)
Source: http://incompetech.com/music/royalty-...
Artist: http://incompetech.com/
All other music by Aakash Gandhi
SVG Attributions:
Earth: Designed by Flat Icons from www.flaticon.com, CC BY 4.0 https://creativecommons.org/licenses/by/4.0, via Wikimedia Commons
GPS: Icons made by https://www.flaticon.com/authors/pause08 from https://www.flaticon.com/
Wireless Comms: Design inspired by https://svgsilh.com/image/297434.html
Видео The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever? канала Reducible
We see that the FFT is an incredibly efficient recursive algorithm that performs this task, and we also discover that a slightly tweaked FFT (Inverse FFT) can also solve the reverse problem of interpolation. If this video doesn't blow your mind, I don't know what will.
0:00 Introduction
2:19 Polynomial Multiplication
3:36 Polynomial Representation
6:06 Value Representation Advantages
7:07 Polynomial Multiplication Flowchart
8:04 Polynomial Evaluation
13:49 Which Evaluation Points?
16:30 Why Nth Roots of Unity?
18:28 FFT Implementation
22:47 Interpolation and Inverse FFT
26:49 Recap
Also a subtle mistake that a commenter made me aware of -- at 26:40 instead of replacing w with (1/n * e^{-2 * pi i/ n}), the actual right way to do this is by taking the final output of the IFFT at the end of the recursion and dividing by n.
So the full change is w = e^{-2 pi i / n}
And then somewhere outside the scope of the IFFT function ifft_result = 1/n * IFFT(values)
The treatment of the FFT in this video is inspired by several well known references, mainly Introduction to Algorithms (Cormen et al.) and Algorithms (Papadimitriou et al.).
Support: https://www.patreon.com/reducible
This video wouldn't be possible without the open source manim library created by 3blue1brown: https://github.com/3b1b/manim
Here is link to the repository that contains the code used to generate the animations in this video: https://github.com/nipunramk/Reducible
Elegant proof that the matrix used in the proof that (d + 1) points uniquely define a degree d polynomial is invertible: https://math.stackexchange.com/questions/426932/why-are-vandermonde-matrices-invertible
Music:
Lift Motif by Kevin MacLeod is licensed under a Creative Commons Attribution license (https://creativecommons.org/licenses/...)
Source: http://incompetech.com/music/royalty-...
Artist: http://incompetech.com/
All other music by Aakash Gandhi
SVG Attributions:
Earth: Designed by Flat Icons from www.flaticon.com, CC BY 4.0 https://creativecommons.org/licenses/by/4.0, via Wikimedia Commons
GPS: Icons made by https://www.flaticon.com/authors/pause08 from https://www.flaticon.com/
Wireless Comms: Design inspired by https://svgsilh.com/image/297434.html
Видео The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever? канала Reducible
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
But what is the Fourier Transform? A visual introduction.3. Divide & Conquer: FFTTowers of Hanoi: A Complete Recursive VisualizationSo how does a PS/2 keyboard interface work?FFT in excel for spectral analysisCan you GROW an Opal?Hamming codes and error correctionWhen the FBI had too many fingerprints in storage | The mathematics of image compressionBranchless Programming: Why "If" is Sloowww... and what we can do about it!A Strange But Elegant Approach to a Surprisingly Hard Problem (GJK Algorithm)This completely changed the way I see numbers | Modular Arithmetic Visually ExplainedDenoising Data with FFT [Python]But what is a Fourier series? From heat flow to drawing with circles | DE4What Is Big O Notation?Introduction to Graph Theory: A Computer Science PerspectiveTI Precision Labs – ADCs: Fast Fourier Transforms (FFTs) and WindowingWhat is a Fourier Series? (Explained by drawing circles) - Smarter Every Day 205Why do prime numbers make these spirals? | Dirichlet’s theoremFourier Transform, Fourier Series, and frequency spectrum5 Simple Steps for Solving Any Recursive Problem