A Linked List Sparse Matrix Implementation Solution

Summary.  Many real-world applications rely on processing of large 2D matrices that often

have few non-zero elements relative to the total number of entries in the matrix.  For Project #3, you will use linked lists to implement a memory-efficient, sparse 2-dimensional matrix data structure. Then, you will test your data structure by loading in some large 1000x1000 matrices, which we have constructed to contain hidden patterns that will be visible if you have implemented your matrix correctly.

 

Overview of a Linked List Sparse Matrix Data Structure Design.

 

A typical linked list implementation of a sparse matrix relies on two sets of interconnected linked lists: one for the rows of the matrix, and one for the columns of the matrix.  On both sides, an array can be used to keep track of the heads of each linked list, and each element is part of one column linked list as well as one row linked list.  An example of the logical structure a linked list is shown below for a 5x5 matrix (Figure A).

 Each of the matrix elements will need to store their data, row and column indices, and two links: one to the next element in that column (if it exists) and one to the next element in that row (if it exists) (Figure B). The data for the element (1,0) of the sparse matrix is shown as an example in Figure C.  Your goal will be to implement a class MatrixEntry that stores all of this information as well as a class SparseIntMatrix that implements the linked list structure shown above.

 

 

Part I. (20 points) Defining and Implementing a MatrixEntry class

 

The MatrixEntry class contains all of the data members necessary for storing the data and links for each element of the sparse matrix.  Define and implement this class including the following methods:

 

•     Name:  MatrixEntry(int row, int col, int data) (constructor);  input: the row, column, and data associated with this matrix element; output: an instance of the MatrixEntry class

 

•     Name: getColumn(); input: none; output: an integer corresponding to the column of this entry

 

•   Name:  setColumn(int col);  input: integer corresponding to the column of this entry;

output: none

 

•   Name: getRow(); input: none; output: an integer corresponding to the row of this entry

 

•   Name: setRow(int row); input: integer corresponding to the row of this entry; output:

none

 

•     Name: getData(); input: none; output: an integer corresponding to the data associated with this entry

 

•   Name: setData(int data); input: integer with the data for this matrix entry; output: none:

 

•     Name: getNextColumn(); input: none; output: a reference to the next matrix element in the current element’s column

 

•     Name:  setNextColumn(MatrixEntry el); input: MatrixEntry reference of next element in this element’s column; output: none

 

•     Name: getNextRow(); input: none; output: a reference to the next matrix element in the current element’s row

 

•     Name:  setNextRow(MatrixEntry el); input: MatrixEntry reference of next element in this element’s row; output: none

 

Data members:  any that are necessary to maintain the object’s state and implement the methods above. The MatrixEntry class should be defined as a separate class from the SparseIntMatrix class described below, and all data members should be declared private.  Your

rSparseIntMatrix class client should interact with MatrixEntry objects through the public accessor/mutator methods.

 

Part II.  (60 points) Defining and Implementing a SparseIntMatrix class

 

Your second goal is to design and implement the SparseIntMatrix class, which should provide the basic functionality of a matrix, but use the linked list structure described above (NOTE: you should not just use a 2D array here—you will receive 0 points for a 2D array-based solution).

 

The SparseIntMatrix class should have all of the following methods:

 

•     Name:  SparseIntMatrix(int numRows, int numCols) (constructor); Input: integers with the number of rows and number columns in this matrix;  output: instance of this class

 

•   Name:  SparseIntMatrix(int numRows, int numCols, String inputFile) (constructor);  Input:

integers with the number of rows and number columns in this matrix, and a String with the filename of a file with matrix data. The format of the input file should be comma- delimited lines with the row,column,data of each element. This constructor should populate the matrix with this data; output: instance of this class

 

•   Name: getElement(int row, int col); input: integers with the row and column of the

desired element; output: corresponding element (integer) if one exists or zero otherwise.

 

•     Name: setElement(int row, int col, int data); input: integers with the row and column of the element to be set and an integer with the matrix data;  output:  boolean indicating if operation was successful (e.g. row/col were in the correct range)

 

•     Name: getNumCols(); input: none; output: integer with the number of columns in this matrix

 

•   Name: getNumRows(); input: none; output: integer with the number of rows in this matrix

 

•     Name: plus(SparseIntMatrix otherMat); input: another sparse matrix to be added to the current one. This method should update the state of the current object;  output: boolean indicating if addition was successful (matrices should be identical dimensions)

 

•     Name: minus(SparseIntMatrix otherMat); input: another sparse matrix to be subtracted from the current one. This method should update the state of the current object;  output: boolean indicating if addition was successful (matrices should be identical dimensions)

 

Data members:  any that are necessary to implement the methods above using the linked list structure shown in Figure A.  All data members should be declared private.

 

 Part III. (10 points) Testing your SparseIntMatrix Implementation

 

Now that you’ve finished implementing the SparseIntMatrix class, write a main method in a separate class to test its functionality. We have provided three data files for you to test your implementation: matrix1_data.txt, matrix2_data.txt, and matrix2_noise.txt.  All three of these files are comma-delimited with the following format on each line: <row,<column,<matrix element, and they each contain a 1000x1000 sparse integer matrix.

 

We have also provided a helper class MatrixViewer and EasyBufferedImage which will allow you to visualize the patterns in these matrices.  If you have implemented your matrix construction correctly matrix1_data.txt  will contain an obvious pattern, which you can view by putting the following code inside a main method:

 

SparseIntMatrix mat = new SparseIntMatrix(1000,1000,"matrix1_data.txt"); MatrixViewer.show(mat);

 

Matrix2_data.txt also contains a pattern, but it is obscured by random noise.  All you’ll need to do is load in the matrix in matrix2_noise.txt and subtract this matrix off of matrix2_data (i.e. matrix2_data.minus(matrix2_noise).  Check for a pattern before and after removing the noise— if you’ve implemented your matrix arithmetic correctly, the pattern should be obvious.  Be sure

to save all of the code that you use to check these patterns in your main method. To receive the full 10 points for this section, you must successfully load and properly use all three example files described above.

 

Part IV. (10 points) Analysis and Comparison of Space Efficiency of your SparseIntMatrix class

 

Answer the following questions about the memory used by your SparseIntMatrix implementation relative to a standard 2-dimensional integer array.  Please include your answers in the header of your SparseIntMatrix.java file.

 

Assume that for the MatrixEntry class, each of the following require 1 memory unit:  row label, column label, matrix element data, link to next row element, link to next column element. Ignore the overhead of the array that stores the links to the row/column linked lists— only consider the memory used in storing matrix elements.  Also, you can assume that each element of a 2D

array will require 1 memory unit.  Be sure to justify how you arrived at your answers to receive full credit.

 

(a) For a square matrix of N x N elements with m non-zero elements, how much memory is required for the SparseIntMatrix implementation? How much for a standard 2D array implementation?

 

(b) For a square matrix, assume N=100,000  and m=1,000,000. Is the SparseIntMatrix implementation more space-efficient, and if so, by how much? (i.e. was it worth all of the effortyou just went through implementing it?)  For what value of m does the 2D array implementation become more space-efficient than the SparseIntMatrix implementation?

 

Submitting your finished assignment:

 

Once you’ve completed Project #3, create a zip file with all of your Java files (.java) and submit them through Moodle.

 

Working with a partner:

 

As discussed in lecture, you may work with one partner to complete this assignment (max team size = 2). If you choose to work as a team, please only turn in one copy of your assignment. At the top of your class definition that implements your main program, include in the comments both of your names and student IDs. In doing so, you are attesting to the fact that both of you have contributed substantially to completion of the project and that both of you understand all code that has been implemented.