**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.