Reference no: EM13332239

Motivation

A sparse matrix is defined as a matrix in which a significant number of the elements are set to some base value, 0 for most applications. This provides an excellent opportunity for memory savings as we do not always need to represent every element in the matrix. For example, consider the following matrix:

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1

At first glance, one might attempt to allocate a 2 dimmensional array of size 4x4 to represent the matrix. While this would provide an adequate solution for a matrix of this small size, imagine a case where a 100000x100000 matrix was filled with only one non-zero value. Obviously, there is room for some simplification here. This is where you come in.

General Description

Your job in this assignment is to create a class for representing and manipulating sparse matrices. Your class should represent the matrix in a manner such as the one described below. This method provides a reasonable savings in memory and, if properly coded, can avoid incurring too much of a speed penalty.

Sparse Array Example

The method to be used in this assignment uses a row simplification in order to reduce the matrix. By eliminating all zeros not contained between non-zero fields, the COLUMNS can be represented by much smaller data sets. This concept is best illustrated by an example.

The following sparse array:

1 0 0 0 1
0 1 1 0 0
0 0 1 0 0
0 1 0 1 1
0 0 0 0 0

Can be represented as follows:

COLUMN Data Offset Size
0 [1] 0 1
1 [1 0 1] 1 3
2 [1 1] 1 2
3 [1] 3 1
4 [1 0 0 1] 0 4

The memory used by this sparce array = 148 bytes

Where Offset, an integer array, represents the number of zeros before the first non-zero element of each COLUMN. Size, an integer array, represents the number of elements in the data set.As you can see, there is no data lost in this simpler representation and some memory savings can already be realized.

Specific Program Requirements

o Your program MUST use COLUMNS of Data to represent the matrix.
o For this program you will have to have a 'set' and 'get' member functions (see 'sarray.h' below) these SHOULD NOT BE called by any of the operator member functions.
o In the 'get' and 'set' member functions 'i' is ROW number and 'j' is the COLUMN number of the element.

example:
0 0 0 0 0
0 0 0 1 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
the only '1' value in this matrix is located at
i=1
j=3

o Your class should implement the member functions defined in sarray.h. DO NOT change the names of these functions.
o Values within the matrix should be stored as double.
o Matrix arithmetic should be performed using operator overloading.
o All operations must be done within the class. ie: no functions to do math outside class.
o You must use new/delete for memory allocation instead of malloc/free or static allocation.