Problem:

Template:

Please Answer Using MATLab Code! Thanks!

Problem Statement Consider a "d-block diagonal" matrix, which is a square matrix made up of smaller square matrices along the diagonal, with zeros everywhere else as shown in the figure below. It has d inner blocks, each of width d, so the total size of the block diagonal matrix is N=d2. The elements in the dd blocks are the only non-zero values. An example is given on the right of the figure below (but it is only for a system with d=3 ). It should go without saying that using nave Gauss Elimination on the system of equations below is a waste of time. Row-eliminating rows that consist of mostly zeroes consumes a lot of computing power for no benefit. Instead, it would be much more efficient to recognize this structure and only row-eliminate the non-zero blocks. In this problem, we will explore how much faster a tuned algorithm will perform on a system with this structure relative to nave Gauss Elimination. To do this, we will also need to generate sample systems of equations that are d-block diagonal. Example of a 3-block diagonal matrix (d=3,N=d2=9) a11a21a31000000a12a22a32000000a13a23a33000000000a44a54a64000000a45a55a65000000a46a56a66000000000a77a87a97000000a78a88a98000000a79a89a99 Objectives Using the information presented in the problem statement, you are to: 1. Create a function that generates a d-block diagonal matrix A of random numbers, where the user can input the block size, d. The function should also output a right-hand-side vector b of random numbers, and thus generates a complete block-diagonal system of linear equations Ax=b. 2. Adapt the nave Gauss Elimination algorithm to exploit the structure of block-diagonal systems. 3. Record the solution time for nave Gauss Elimination and your block diagonal solver for a variety of block sizes. 4. Compare the solution times via a visualization tool and make a conclusion about the computational complexities of both methods. Deliverables You are to submit a code package containing a driver code, a function called MakeBlockDiagonal, a function called BlockDiagonalsolver, and the supplied Gauss Elimination code GE. The driver file must perform the following once the "play" button is pressed: 1. Generate d-block diagonal systems of linear equations Ax=b for d=[5,10,15,,50] and solve each of these systems using both nave Gauss Elimination and your block diagonal solver. 2. Time how long it takes for each method to solve the system of equations for each d. 3. Output A plot of log(t) on the y-axis and log(d) on the x-axis which clearly shows the solution times (t) of your block diagonal solver and nave Gauss Elimination on the same axes. In your cover letter, discuss briefly what your results indicate. Moreover, report the computational complexity of nave Gauss Elimination and your d-block diagonal solver both in terms of block size d. Explain how your plot demonstrates the computational complexities. If there are any discrepancies, explain why that might be the case. Advice - You are to use the provided GE code for Gauss Elimination. - Your block diagonal solver can USE GE. You should not need to modify GE. - You are advised to think of a clever way to generate a d-block diagonal matrix. Do NOT attempt to do it by hand (a 50 -block diagonal matrix is 25002500 ). - When solving for d=[5,10,15,,50], you should be using a loop. - You can time how long a section of code takes to run using tic and toc. - You can make a log-log plot either by taking the log(0 of your data, or by using the function loglog() in MatLAB. - The complete code can take awhile to run (upwards of 2-3 minutes), so consider not simulating for all values of d until your code is running as expected to save waiting time. for k=(i+1):n \% Skips the pivot element and indexes what is BELOW it in the SAME COLUMN as the pivot element. factor =(A(k,i)/A(i,i));% Calculates the row factor for current row for j=1:n \% Column index A(k,j)=A(k,j) factor A(i,j);% Row subtraction, element-by-element end b(k)=b(k) factor (i);% Updates b end end