4. (theoretical, 6 points) In this question, we focus on LU-factorization and that by re-ordering unknowns of the linear system, we can achieve significant savings on the overall computational cost. Consider the following linear system Ax = b: 4 1 1 1||x| [& 1 4 0 0 X2 s bg (*) 1 0 4 0 X3 - bg 1 0 0 4 Xa b4 The LU-factorization of the matrix A 1s as follows: 1 0 0 0 4 1 1 1 1 0 0 0o & 1 _1I =l wa v f i 5 10 0 0 $F % 1 1 1 26 i "5 u 1 00 0 F (1) If we re-arrange the linear system in the reverse order of unknowns, x;. x;, x3, x4, We obtain a new system: > Arevxrev = IEi'rev: 4 0 0 1 X4 b4 0 4 0 1 X3 . bg 0 0 4 1||x]| " |b) 1 1 1 4f|x b, Now you are asked to find (by hand) the LU-factorization of A,.,. Show your steps. \"You may try closer initial guesses, like 6 0,001, but you will nevertheless get diverging iterations. You need to argue both directions, ie., (1) if x* is a root of f(x), it is also a fixed point of g(x) and (2) if x* is a fixed point of g(x), it is also a root of f(x). (2) An immediate observation on the LU-factorization of Arey is that a lot of steps are unnecessary and hence a lot of floating point operations can be saved. Now, consider the following matrix that generalizes the pattern of Arev: ain a11 0 a2n azz 0 0 a33 Ageneral = . . . 0 0 0 an-1.n-1 an-1,n ann an1 an3 an,n-1 an2 Essentially, nonzero entries only locate on the diagonal, the last column and the last row of the matrix. You are now asked to find the total number of floating point operations (flops) involved in the LU-factorization of Ageneral (with the unnecessary steps excluded). (3) The savings in the previous question are not possible for the original matrix A in eq. (+) or general matrices with A's pattern. Briefly explain why.(4) When a matrix has a large number of zero entries, it's called a sparse matrix. The memory requirement of such matrices can be reduced by storing only nonzero entries and their indices. In MATLAB, the sparse function can convert a matrix to be stored according to its sparsity (without changing the contents of the matrix of course). Here is an example matrix using Ageneral's sparsity pattern and n = 5. N=5; A = diag (randi ([50 , 100] , N, 1)); A (1 : end -1 , end) = randi ([1 , 10] , N-1, 1) ; A (end , 1 : end -1) = randi ([1 , 10] , 1, N-1) ; sparse_A = sparse (A); 93 60 80 53 sparse_A = Compressed Column Sparse (rows = 5, cols = 5, nnz = 13 [52x]) 93 80 53 We set n = 1000 for more sparsity and see the memory reduction achieved by sparse: Attr Name Size Bytes Class A 1000 x1000 8000000 double sparse_A 1000x1000 55976 double Storing the full matrix (including all the zeros) needs roughly 8MB whereas the sparse version needs roughly 55KB. In light of this, can you point out another potential benefit of using the re-ordering scheme we looked at in this