Differences

This shows you the differences between two versions of the page.

--- math105-s22:s:jianzhi:start [2022/04/28 04:45]
jianzhi [FFT, Wavelet Transformation, Uncertainty Principle (The Last Presentation)]
+++ math105-s22:s:jianzhi:start [2026/02/21 14:41] (current)
@@ Line 737: / Line 737: @@
 Remark: This problem is also equivalent to evaluating a polynomial at the roots of unity, the so-called changing from coefficient representation to value representation.
-**Fast Fourer Transform**
+**Fast Fourier Transform**
 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**
-$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$.

Lecture Notes