#!/usr/bin/env python
# coding: utf-8

# ### **Note** 
# * All items of problems in problem sets should be done in seperate cells.
# * Do not forget to include title, labels of each line and set axis names for every figure you plot.
# * If most part of your plot is very close to $0$, it might be a good idea to use logarithmic scale.
# * You can submit incomplete problems. They will be graded as well.
# * Bonus tasks are challenging and non-obligatory. However, they may help you with your final grade.

# # Problem 1 (Fast Fourier transform)

# ## 25 pts
# 
# * 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 <font color=red>does not utilize full matrices </font> 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.

# In[ ]:





# # Problem 2 (Strassen algorithm)

# ## 25 pts
# 
# * Implement Strassen algorithm. For simplicity consider that n is a power of 2
# * Compare your implementation the Strassen algorithm with direct matrix-matrix multiplication using loops and `𝚗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$. 
# * Find analytically constant outside $n^3$ after $2$ levels of the Strassen algorithm. Compare it with $2n^3$ in the naive version.

# In[ ]:





# # Problem 3 (Fast convolution)

# ## 30 pts
# 
# #### 1D
# 
# * 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.
# 
# #### 2D
# 
# * Find convolution of the Lena $n\times n$ image and the following filter
# $$
# T_{i_1j_1i_2j_2} \equiv T_{i_1-j_1,i_2-j_2} = \frac{\alpha}{\pi} e^{-\alpha \left[(i_1 - j_1)^2 + (i_2 - j_2)^2 \right]}, \quad i_1,j_1, i_2, j_2 = 1,\dots, n, \quad \alpha = \frac{1}{50}
# $$
# 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?

# In[ ]:





# # Problem 4 (SVD intro)
# 
# ## 20 pts
# 
# * Find SVD decomposition of the Lena image and plot its singular values.
# * Compress the image using trunction of singular values. Plot compressed images for several $r$ ($r$ is a number of remaining singular values). Specify in titles of images compression rate. **Note:** do not forget to use `plt.subplots`.

# In[ ]:





# # Bonus Problem (HOSVD)

# 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](http://ca.sandia.gov/~tgkolda/pubs/pubfiles/TensorReview.pdf) on Figure 4.3.

# In[ ]: