Implement matrix version of the Cooley-Tukey FFT algorithm (see lecture 4). This means that your goal is to write a function that has vector as an input and its discrete Fourier transform as an output. Make sure that your algorithm does not utilize full matrices and your complexity is $\mathcal{O}(n \log n)$. For simplicity consider that $n$ is a power of $2$
Compare timings of your algorithm with those of np.dot
and np.fft.fft
by plotting timings as a function of $n$. Was it a good idea to implement your own version of the FFT? :)
The overall complexity of FFT algorithm is $\mathcal{O}(n \log n)$. Find analytically constant hidden in $\mathcal{O}(\cdot)$ for the Cooley-Tukey version.
𝚗p.𝚍𝚘𝚝
function by ploting timings as a function of $n$.It might be a good idea not to do recursion in the Strassen algorithm to the bottom level. Sometimes only several levels of the recursion are used. This helps to reduce a constant outside $n^3$.
Implement fast multiplication of a Toeplitz matrix by a given vector with $\mathcal{O}(n \log n)$ complexity. Make sure that you do not form the Toeplitz matrix itself!
Now you are able to implement Problem 1 from the Problem Set 1 without truncating the signal. Convolve your signal with the filter $T$ using your fast multiplication algorithm (set $\alpha=\frac{1}{20}$). Play the signal.
with $\mathcal{O}(n^2 \log n^2)$ complexity. Plot the resulting image (plt.imshow
might be helpful for this task). What is the complexity of naive summation?
plt.subplots
.
Implement High-Order SVD (HOSVD) algorithm in 3D. As an output give ranks of the 3D Hilbert tensor $$ a_{ijk} = \frac{1}{i+j+k + 1}, \quad i,j,k = 0,\dots, 199 $$ with $10^{-5}$ accuracy. Details can be found here on Figure 4.3.