Description

CS 610 104 Programming Project (Spring 2017)

Sparse Matrix Data Type

A matrix Am,nis a rectangular array of m x n numbers (m, n > 0). Matrices play an important role in computer

science. They are used in algorithms for numerical problems, graphs, pattern recognition, image processing, etc. A

sparse matrix is a matrix where a large number of the elements have a value of zero. The naïve approach of

implementing a sparse matrix is to use a 2D array. However, when working with very large sparse matrices with

thousands (or millions, or billions) of rows and columns, significant space is wasted by storing zero values. The

matrices below, A and B, are two small examples of sparse matrices (though they are not very sparse).

A = [

3 0 0 5

0 2 −7 0

5 −3 0 0

0 6 0 −5

] , B = [

1 0 0 0 1 0

0 1 0 0 0 1

0 0 1 0 0 0

1 0 0 1 0 0

]

There are several mathematical operations defined for a sparse matrix data type, including scalarMultiply(c),

add(M), subtract(M), multiply(M), power(p), and transpose().

There are many different data structures that can be used to implement a sparse matrix. In this project you will use

an array-based data structure. The array representing the sparse matrix will store Matrix Entries, each of which

consists of a value (a non-zero integer), a row (a positive integer), and a column (a positive integer). The Matrix

Entries are stored in the array in non-decreasing order according to their row and are subsorted in non-decreasing

order according to their column. The table below illustrates matrix A in this data structure. Note that the size of the

array is intended to be significantly smaller than m * n in most cases.

Index 0 1 2 3 4 5 6 7

row 1 1 2 2 3 3 4 4

column 1 4 2 3 1 2 2 4

value 3 5 2 -7 5 -3 6 -5

The end goal of this project is to have a program that can represent any m x n matrix and be able to perform

mathematical operations on sparse matrices. There are several operations defined for a sparse matrix data type.

SparseMatrix(S) Initializes a sparse matrix using a comma-delimited string S in the following format: “nricj,

nricj, nricj, ...”, where n is an integer indicating the value, i is an integer indicating the row,

and j is an integer indicating the column. The entries in S are in no pre-defined order, so

you will need to take that into account. Matrix A from Page 1 could be stored as:

-5r4c4, 5r1c4, 2r2c2, 5r3c1, -3r3c2, 6r4c2, -7r2c3, 3r1c1

Note that the size of the matrix m x n can be determined based on the entries in S. In the

above example, you can find m = n = 4.

SparseMatrix(m, n) Initializes an empty sparse matrix with m rows and n columns. To be used when initializing

a result Sparse Matrix in add, subtract, multiply, etc.

print() Prints the Sparse Matrix to standard output. Note that zeros need to be printed in print().

Additionally, your print operation will need to print the matrix so it looks like a matrix. If

there are more than six rows only print the first two rows and the last two rows, separated

by ... in one intermediate row. If there are more than six columns only print the first two

columns and the last two columns, separated by a ... in one intermediate column. NOTE:

print only prints, it does not return any value (e.g., a string).