Now we are going to see how the computational complexity scales with the size of our...

 

Transcribed Image Text:

Now we are going to see how the computational complexity scales with the size of our Nx N matrix. Write a loop from N=1 to 100 that: creates matrix of size N with random entries, calls GE_count for each matrix, saves the number of operations in a vector count vector (one entry for each matrix) define a vector, Nvector from 1 to 100 You can generate random matrices of size Nx N by using the MATLAB command: rand (N). Make a plot of the size of the matrix (x-axis) by the number of scaling operations and number of subtraction/replacement operations (y-axis). Use the commands figure (1) %generates a new figure plot (Nvector, countvector) %Nvector and count vector need to be the same length xlabel ('Size of Matrix, N') ylabel('Number of operations') title('Computational complexity of GE') (c) Do the operations both grow like O(N)? Plot on a log-log scale to check. You can also plot (N vs N) to compare the slope. The command for plotting on log-log is loglog(x,y). (d) Find the number of necessary floating point operations required to com- pute the following operations (using the big-oh notation introduced in class). Explain your reasoning in each case. (a) Compute the sum A + B for A, B = Rmxn. (b) Compute the product Ax for x E Rn and A E Rnxn where A is upper triangular. Now we are going to see how the computational complexity scales with the size of our Nx N matrix. Write a loop from N=1 to 100 that: creates matrix of size N with random entries, calls GE_count for each matrix, saves the number of operations in a vector count vector (one entry for each matrix) define a vector, Nvector from 1 to 100 You can generate random matrices of size Nx N by using the MATLAB command: rand (N). Make a plot of the size of the matrix (x-axis) by the number of scaling operations and number of subtraction/replacement operations (y-axis). Use the commands figure (1) %generates a new figure plot (Nvector, countvector) %Nvector and count vector need to be the same length xlabel ('Size of Matrix, N') ylabel('Number of operations') title('Computational complexity of GE') (c) Do the operations both grow like O(N)? Plot on a log-log scale to check. You can also plot (N vs N) to compare the slope. The command for plotting on log-log is loglog(x,y). (d) Find the number of necessary floating point operations required to com- pute the following operations (using the big-oh notation introduced in class). Explain your reasoning in each case. (a) Compute the sum A + B for A, B = Rmxn. (b) Compute the product Ax for x E Rn and A E Rnxn where A is upper triangular.