math105-s22:s:jianzhi:start
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
math105-s22:s:jianzhi:start [2022/04/28 04:46] jianzhi [FFT, Wavelet Transformation, Uncertainty Principle (The Last Presentation)] |
math105-s22:s:jianzhi:start [2026/02/21 14:41] (current) |
||
|---|---|---|---|
| Line 741: | Line 741: | ||
| A naive implementation of the Discrete Fourier Transform takes $O(N^2)$. However, Fast Fourier Transform performs it in $O(N log N)$ by exploiting the symmetry of the roots of unity. | A naive implementation of the Discrete Fourier Transform takes $O(N^2)$. However, Fast Fourier Transform performs it in $O(N log N)$ by exploiting the symmetry of the roots of unity. | ||
| - | An illustration of idea is: break down the polynomial into even and odd terms. We can recycle many computations. Use 1 and -1 as an example. | + | An illustration of idea is: break down the polynomial into even and odd terms. We can recycle many computations. Use $1$ and $-1$ as an example. |
| **Inverse Fourier Transform** | **Inverse Fourier Transform** | ||
| - | $y_j = \frac{1}{N} \Sigma_{k=0}^{N-1} c_k e^{\frac{2 \pi ijk}{N}$ | + | $y_j = \frac{1}{N} \Sigma_{k=0}^{N-1} c_k e^{\frac{2 \pi ijk}{N}}$ |
| The trick here is to notice that the inverse matrix is just another Vandermonde matrix with $\bar{\omega}$ instead of $\omega$. | The trick here is to notice that the inverse matrix is just another Vandermonde matrix with $\bar{\omega}$ instead of $\omega$. | ||
math105-s22/s/jianzhi/start.1651121171.txt.gz · Last modified: 2026/02/21 14:43 (external edit)
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
