[SOLVED] Amath 481 / 581 homework 3 – sparse matrices and fft

(1) The time evolution of the vorticity ω(x, y, t) and the streamfunction ψ(x, y, t) are given by the
governing equations:
ωt + [ψ, ω] = ν∇2ψ (1)
where [ψ, ω] = ψxωy − ψyωx and ∇2 = ∂
2
x + ∂
2
y
. The streamfunction satisfies
∇2ψ = ω. (2)Boundary Conditions: Assume periodic boundary conditions for both the vorticity and the streamfunction.
(a) Using the spdiags command, generate the three matrices A = ∂
2
x + ∂
2
y
, B = ∂x and C = ∂y which take
derivatives in two dimensions. Use the discretization of the domain and its transformation to a vector as in
class.ANSWERS: With x, y ∈ [−10, 10], n = 8 save the matrices A, B and C as A1, A2 and A3 respectively.NOTE: You can’t write out sparse matrices to ASCII files so be sure to first make the matrices full, i.e. you
can use A=full(A) in MATLAB and it will turn a sparse matrix into a full matrix.
Centered Fourier Matrix
center center
1
….
5
….
….
9
….2 Permutation
3
4 16
13
14
15
12
2
8
4
1
12
Figure 1: Encryption of the Fourier matrix.(2) Fourier Transform (FFT) of an image is sometimes used for image encryption. The idea for the encryption is to divide the image in Fourier space into blocks. Permuting the blocks and applying the inverse
FFT will result in a scrambled image instead of the original one. The image can be decrypted with the inverse
permutation (key).The motivation for the encryption is based on the fact that guessing the permutation
takes a long time, since each guess involves an inverse FFT operation. Most images include low frequency
components so it is enough to choose squared blocks in the center of the (centered) Fourier matrix of the
image and permute them as shown in Fig. 1.(a) Write a decryption algorithm that gets as an input a (centered) Fourier matrix 400 × 400 and an
inverse permutation vector that specifies how 16 blocks of 20 × 20 should be permuted back to their original
placement.The algorithm will permute the blocks, shift the Fourier matrix from the center to the corners and perform inverse FFT to recover the image. Load the Fourier matrix and the permutation vector
from the files Fmat.mat and permvec.mat. Do not turn in these files to gradescope and do not assume
that on gradescope the matrix/vector will have the same elements, thereby plan your algorithm to be general.ANSWERS: Save the absolute values of the decrypted (centered) Fourier matrix as A4 and the reconstructed image matrix (absolute value without uint8) as A5.NOTE: To plot the image matrix (for checking how your decryption works) use the
set(gcf,’colormap’,gray);imagesc(…); or imshow commands. For the plotting, don’t forget to take
absolute values of the reconstructed image and to use uint8. The ind2sub command can be useful for
indexing.