Due: Thursday, 5 October
Matrix Multiplication. In this example you will use Fortran to create two square matrices
B with dimensions
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
1a) How many megabytes of RAM will be required to store matrices
C in the computer's memory for a given matrix size
n? State the formula.
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
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
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
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 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
1i ) If all elements of
B to have the value 1, what value should any element of
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
read statement pair that asks you to input the matrix size
- use an
allocate statement to allocate matrices
- assign all elements of matrices
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
- write out the values of
time to the shell in a user friendly form.
- save the first ten rows and first five columns of
C to a file called
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
MatrixMultiplyTimers.txt into MATLAB and plot
n on a log-log plot. Save the MATLAB figure to a file called
3c) Based on these results and the big-O scaling, how long do you think it would
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.