Due: Thursday, 5 October

Matrix Multiplication. In this example you will use Fortran to create two square matrices `A` and `B` with dimensions `n` x `n`. You will then use matrix multiplication to compute their product with the results being stored in matrix `C`. Thus, you will be computing the matrix equation `C = AB`. Note that matrix multiplication is different from element by element array multiplication. See the wikipedia page if you are unsure what matrix multiplication is.

Part 1 - Analyze the problem

For this part, list your answers in a plain text file called `answers_part1.txt` and submit that file to github in a new folder named `assignment_5`.

1a) How many megabytes of RAM will be required to store matrices `A`,`B` and `C` in the computer's memory for a given matrix size `n`? State the formula.

1b) Element `C(i,j)` is equal to the sum of `A(i,k)*B(k,j)` over all values of index `k` from 1 to `n`. How many multiplication operations does it take to compute the single element `C(i,j)`? How many addition operations does it take to compute the single element `C(i,j)`?

1c) Write down the code snippet for computing element `C(i,j)` using a `do` loop. Assume i and j are given fixed values so you don't need to loop over i or j here.

1d) State the code for computing element `C(i,j)` where you use the intrinsic function `sum` instead of a `do` loop.

1e) Now state the code snippet for computing every element in matrix `C` using your answer from 1c) or 1d) as a starting point. You don't need to write down the entire Fortran program. Just state the part that performs the matrix product `C = AB`.

1f) How many total operations does it take to compute the matrix product `C = AB`? State your answer as a single formula in terms of `n`.

1g) Simplify your result from 1f) by stating it using big-O notation. In big-O notation you just state the dominant term and ignore any constants. Write your answer as O(`X`), where `X` is the dominant term.

1h) Big-O notation is used to classify the performance of an algorithm as a function of the size of the input `n`. Assume your matrix product algorithm will take time `t0` to run on your computer when `n=1`. How long should it them take for `n=10,n=100,n=1000`?

1i ) If all elements of `A` and `B` to have the value 1, what value should any element of `C` be?

Part 2 - Write the code

2) Now that you have all the pieces, write a Fortran program named `MatrixMultiply.f90` that computes `C=AB` for the `n x n` matrices `A,B,C`. Your program should - Have a `write` and `read` statement pair that asks you to input the matrix size `n` - use an `allocate` statement to allocate matrices `A,B,C` - assign all elements of matrices `A` and `B` to have the value 1. - use the answer from exercise 1e) to carry out the matrix multiplication - use calls to `cpu_time()` before and after the do loops to assign the time it takes to compute `C=AB`. Save this time to a variable called `time` - write out the values of `n` and `time` to the shell in a user friendly form. - save the first ten rows and first five columns of `C` to a file called `C.txt`

Part 3 - Analyze the results

3a) Create a text file named `MatrixMultiplyTimers.txt` that lists the timing results for `n=10, n=100, n=1000` with columns for the values `n` and `time`.

3b) Load `MatrixMultiplyTimers.txt` into MATLAB and plot `time` versus `n` on a log-log plot. Save the MATLAB figure to a file called `MatrixMultiplyTimers.pdf`.

3c) Based on these results and the big-O scaling, how long do you think it would take for `n=10000` and `n=100,000`. How much RAM would you need on your computer for these two cases?

Part 4 - Turn it in

Put all the files created for this assignment into a folder called assignment_5 and upload that folder to your github repository.