Sparse Matrix Multiplication using MPI

In this assignment, you will implement a sparse matrix multiplication algorithm of your choice using MPI.
Unlike dense matrix operations, sparse matrix operations will force you to use more sophisticated data structures and
force you to think about load balance.

You may work with a partner if you wish.

1 Background

A sparse matrix is one that is populated with many zeros. Large sparse matrices are often encountered in science and
engineering when solving partial differential equations, and special data structures are used to compactly represent
such matrices. Sparse matrices can have a wide range of sparsity, which is defined as the percentage of zero entries
with respect to the total number of entries in the matrix. Thus, a sparsity value of 90% means that 90% of the matrix
entries are zeros. For this assignment, you can assume that sparsities are at least 70%.

2 Sparse Matrix Multiplication Algorithms

You may use any sparse matrixmultiplication algorithmthat you wish, so you are free to consult the literature or devise
your own algorithm. However, you are not allowed to reuse existing code except to translate and generate matrices.
To help you get started, you might find the following material useful:

3 Sparse Matrix Representation

Many sparse matrix representations have been proposed, and you may use the format of your choice. In a day or two,
we will provide a few input sparse matrices that use the Matrix Market Exchange Format (MMEF), which you can
use to test your correctness and performance. Of course, when we grade your solutions, we will not limit ourselves to
these few test cases. To learn more about sparse matrix formats, including the MMEF, please see the following URL:

Because we are allowing you to choose your representation, you may find the following library useful, because it
claims to be able to translate among matrices of multiple formats:

4 Generating Large Matrices

You can expect the sparse matrix dimensions to range from 1000 to 10000. The TA’s page will point you to a tool
(written in Fortran) that randomly generates sparse matrices. You can use this tool to generate input matrices with
varying sparsities.

4.1 Matrix Assumptions
• You should not assume any special matrix properties, For example, you cannot assume that the matrices are
symmetric, diagonal, banded, etc.
• You can assume that each matrix elements is a double data type.
• The sparsity may be as low as 70%, which is to say that you can’t make any strong assumptions about sparsity.

5 Details

As usual, you may develop your code on any platform, but we will use the Lonestar Linux cluster at TACC to grade
your solutions, so be sure that what you send us works on Lonestar. You can access the machine by ssh-ing to
. The Lonestar userguide, which is available at the following URL:  provides tips for compiling and running jobs (in
batch mode).

Important: Your solution should include code that reports the elapsed time for your multiplication, excluding file
I/O time. To allow us to check for correctness, your solution should write the final result to a file in MMEF’s Coordinate
Format, and all row coordinates should be listed in increasing order, and within each row all column coordinates
should be given in increasing order.

What to Turn In

This assignment is due at 11:59pm on the due date. Use the turnin program to submit your solution, which should
include the following:

1. A written report of the assignment in either plain text or PDF format. This is your chance to explain your
approach, any insights gained, problems encountered, etc. Your report should include performance results for
your solution.
2. Your source code, instructions to build it on Champion, and instructions to run the programs (along with the
arguments, etc).
3. A file called submit.info. This file should have three lines:
Line 1: Full name of first student
Line 2: Full name of second student (leave a blank line if there is no second student)
Line 3: email id of first student, email id of second student

If you want to use any late submission days, please email the TA, because the turnin program will be disabled at
midnight of the due date, so you will have to mail your work to the TA to turn it in late.