ECE2036 Lab 5 : Sparse Matrices

Due Date: March 30, 2018

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 dimensional 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 rows can be represented by much smaller data sets. This concept is best illustrated by an example.

The following sparse matrix:

1 0 0 0 0

0 1 0 1 0

0 1 1 0 0

0 0 1 0

0 0 1 0

Can be represented as follows:

Row Data Offset Size

[1] 0 1

[1 0 1] 1 3

[1 1] 1 2

[1] 3 1

[1 0 0 1] 0 4

Where Offset, an integer array, represents the number of zeros before the first non-zero element of each row. Size, an integer array, represents the number of elements in the data set.

The memory used by this sparse matrix can be broken down as follows. The integer arrays (4 bytes per integer) storing the offsets and sizes utilize 20 bytes each, for a total of 40 bytes. The Data array, which is an array of pointers to doubles (assuming the data elements are stored in double precision format) contains 5 pointers to each of the dynamically allocated row-data chunks of memory (the sub-rows). On a 32-bit machine, a single pointer requires 4 bytes, and on a 64-bit machine, a single pointer requires 8 bytes.

As such the Data array itself utilizes 20 bytes on a 32-bit machine or 40 bytes on a 64-bit machine. Finally, the individually allocated row-data blocks which are pointed to by each element of this data pointer array, store 11 double precision numbers (8 bytes each), for a total of 88 bytes. Adding up all these contributions yields 40 + (20 or 40) + 88 = 148 or 188 bytes depending on the machine architecture. In both cases, though, even for such a small 5x5 example, this is still less memory than a full 5x5 array of doubles which would consume 25*8=200 bytes of memory. As the matrix size grows, the relative memory savings can become far more considerable. Specific Program Requirements

The declaration of the sparse matrix class is provided already in the file Matrix.h. This class declaration/file SHOULD NOT BE CHANGED. o You must implement all member functions/operators declared in Matrix.h that are not already defined inline or in the provided Matrix.cpp start code. DO NOT CHANGE the prototypes of these functions.

The class includes member functions 'set' and 'get' to manipulate individual matrix elements (see provided 'Matrix.h'). We provide 'get' but you must provide 'set'. These SHOULD NOT BE called by any of the operator member functions. The operator member functions must work directly with the internal class structures which store the matrix data rather than interface through get/set which are intended only for the outside user of your class to manipulate individual elements at a time.

For the 'get' and 'set' member functions, the first input index is the row number and the second input index is the column number.

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 indices (1,3) o All operations must be done within the class. i.e.: no functions to do math outside class.(Example for the LHS scalar multiply function). o You must use new/delete for memory allocation instead of malloc/free or static allocation.

MATRIX.cpp

#include "Matrix.h"

Matrix::Matrix(int rows,int columns) { if (rows>0 && columns>0) { this->rows=rows; this->columns=columns; offset=new int[rows]; size=new int[rows]; data=new double *[rows]; for (int row=0; rowrows=0; this->columns=0; offset=nullptr; size=nullptr; data=nullptr; } }

void Matrix::clear() { for (int row=0; row

int Matrix::memoryUsed() const { int bytes=0; bytes+=rows*sizeof(int); //Memory used by dynamic array of sizes bytes+=rows*sizeof(int); //Memory used by dynamic array of offsets bytes+=rows*sizeof(double *); //Memory used by dynamic array of pointers for (int row=0; row

double Matrix::get(int row,int column) const { if (row<0 || row>=rows) return 0.0; column-=offset[row]; if (column<0 || column>=size[row]) return 0.0; return data[row][column]; }

Matrix Matrix::operator + (const Matrix & a) const { //Return an empty array if dimensions of operands are not compatible

if (columns!=a.columns || rows!=a.rows) return Matrix(0,0);

//Otherwise, set dimensions of answer to match those of operands

Matrix ans(rows,columns);

//Now perform addition row by row including dyanmic memory //allocation for each corresponding sub-row pointer in data[]. //(Note: this code assumes that entries in size[] have been set // to zero for all rows contaning no non-zero entries)

int start1,start2,start; //Index of first non-zero items of current row //within both operand arrays and the answer array. int stop1,stop2,stop; //Index just past last non-zero item of current //row within both the operand and answer arrays. int column,row;

for (row=0; row

//Skip current row if neither array contains non-zero row items

if (size[row]==0 && a.size[row]==0) { ans.size[row]=0; ans.data[row]=nullptr; continue; }

//Find beginning and end of sub-rows within the two operand arrays

if (size[row]==0) { start2=a.offset[row]; stop2=start2+a.size[row]; start1=stop1=start2; } else if (a.size[row]==0) { start1= offset[row]; stop1=start1+ size[row]; start2=stop2=start1; } else { start1= offset[row]; stop1=start1+ size[row]; start2=a.offset[row]; stop2=start2+a.size[row]; } //Define ITEM_1/ITEM_2/ITEM_ANS (array items at current column/row)

#define ITEM_1 data[row][column- offset[row]] //left operand #define ITEM_2 a.data[row][column- a.offset[row]] //right operand #define ITEM_ANS ans.data[row][column-ans.offset[row]] //result

//Determine beginning and end of sub-row within the answer array

if (start1==start2) { column=start1; while (column=stop1) while (column=stop2) while (column

if (stop1==stop2) { column=stop1-1; while (column>=start1 && column>=start2 && ITEM_1+ITEM_2==0) column--; if (column=start2 && ITEM_2==0) column--; if (column=start1 && ITEM_1==0) column--; stop1=stop2=column+1; }

start= start1<=start2 ? start1 : start2; stop= stop1>=stop2 ? stop1 : stop2 ;

//Allocate memory for data in sub-row of answer array

ans.size[row]= stop-start; ans.offset[row]=start;

if (ans.size[row]==0) { ans.offset[row]=0; ans.data[row]=nullptr; continue; } else { ans.data[row]=new double[ans.size[row]]; } //Compute values in sub-row

for (column=start; column=start1 && column=start2 && column

//Undefine ITEM_1/ITEM_2/ITEM_ANS (not necessary but clean coding)

#undef ITEM_1 #undef ITEM_2 #undef ITEM_ANS }

return ans; }

std::ostream & operator << (std::ostream &os,const Matrix &m) { os << std::endl; os << "----- matrix represented -----" << std::endl; int row,col; for (row=0; row

MATRIX.h

#ifndef _SPARSE_MATRIX_H #define _SPARSE_MATRIX_H

#include

class Matrix { int rows,columns; //Number of rows (height) and columns (width) int *offset; //Offsets of first non-zero element in each row int *size; //Sizes of sub-rows containing first & last non-zero element double **data; //Pointers to dynamically allocated sub-row memory

void deepCopy(const Matrix ©);

public:

Matrix(int rows,int columns); Matrix(const Matrix ©) {deepCopy(copy);} ~Matrix() {clear();}

void operator =(const Matrix ©) {clear(); deepCopy(copy);}

void clear(); int memoryUsed() const;

double get(int row,int column) const; void set(int row,int column,double value);

Matrix operator - () const; //Unary - (negation) Matrix operator + (const Matrix &m) const; //Addition Matrix operator - (const Matrix &m) {return *this+(-m);} //Subtraction Matrix operator * (double scalar) const; //Scalar multiply

friend std::ostream& operator << (std::ostream &,const Matrix &); };

inline Matrix operator * (double scalar,const Matrix &m) {return m*scalar;}

#endif

TEST_MAIN.cpp

//Example main function to test your program: //(we recommend you start changing it a bit to fully // test the functionality of your Matrix class after // you get it working with this simple examle below)

#include #include "Matrix.h"

using namespace std;

int main() { Matrix *t1= new Matrix(10,10); // calls the primary constructor cout << *t1 << endl; // memory used=120 (32-bit) or 160 (64-bit)

t1->set(0, 0, 1.0); t1->set(0, 3, 1.0); t1->set(1, 9, 1.0); cout << *t1 << endl; // memory used=160 (32-bit) or 200 (64-bit)

t1->set(3, 2, 6.0); t1->set(4, 2, 3.0); t1->set(5, 2,-2.0); t1->set(6, 5, 2.0); t1->set(9, 5, 4.0); t1->set(2, 7, 1.0); t1->set(4, 7, 1.0); t1->set(5, 7, 1.0); cout << *t1 << endl; // memory used=288 (32-bit) or 328 (64-bit)

t1->set(6, 5, 0.0); t1->set(5, 7, 0.0); cout << *t1 << endl; // memory used=240 (32-bit) or 280 (64-bit)

delete t1; // calls the destructor t1=new Matrix(3, 3); // calls assignment and primary construtor cout << *t1 << endl; // memory used=36 (32-bit) or 48 (64-bit)

t1->set(0, 0, 1.0); t1->set(2, 0, 2.0); t1->set(1, 2, 3.0); t1->set(2, 2, 3.0);

//At this point: // t1 = 1 0 0 // 0 0 3 // 2 0 3 cout << *t1 << endl; // memory used=76 (32-bit) or 88 (64-bit)

*t1 = (*t1) + (*t1); // calls assignment and addition //And now we should have: // t1 = 2 0 0 // 0 0 6 // 4 0 6 cout << *t1 << endl; // memory used=76 (32-bit) or 88 (64-bit)

*t1 = 3*(*t1); // calls assignment and scalar multiplication //And now we should have: // t1 = 6 0 0 // 0 0 18 // 12 0 18 cout << *t1 << endl; // memory used=76 (32-bit) or 88 (64-bit)

Matrix a(3,3), b=*t1; // calls primary and copy constructors

a.set(0,1,7.0); a.set(2,0,-12.0); *t1=a+b; // calls assignment and addition //And now we should have: // t1 = 6 7 0 // 0 0 18 // 0 0 18 cout << *t1 << endl; // memory used=68 (32-bit) or 80 (64-bit)

*t1 = (*t1)-(*t1); // calls assignment and subtraction //And now we should have: // t1 = 0 0 0 // 0 0 0 // 0 0 0 cout << *t1 << endl; // memory used=36 (32-bit) or 48 (64-bit)

delete t1; // calls destructor return 0; // calls destructor for a and b }