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