Matricesare a useful way to represent linear operations, and have applications in most scientific and
engineering fields. For example, in digital image processing, we can blur an image by updating each
pixeltoaweightedsumofitselfanditseightneighbouringpixels.Ifwerepresentanimageusingan
n-dimensionalvector rwitheachelement representingapixel, thenthisblurringoperationcanbe
wri1enasan n matrix M, with each row representing the weights for summing a pixel and its
neighbours. The blurred image r
J can be wri1en as the multiplication of Mand r, i.e., r
J = Mr. In
many applications, the matrix is ‘sparse’, meaning that most of its elements are zero. For example, the following is a sparse matrix:
1
0
0
0
0
. (1)
The image blurring matrix mentioned above is also sparse, because for each row the weighted sum only
involves one pixel and its eight neighbours. As a result, only nine outof the nelements in a row are
non-zero. Nowadays pictures taken using mobile phones typically have millions of pixels. Therefore,
theimageblurringmatrixishighly sparse,withthemajorityofelementsbeingzeros. Tousesucha
sparsematrixinacomputerprogram,itwouldbeahugewasteof resourcetostoreallitselements.
Instead, weshould only storeitsnon-zero elements, as wellastheirpositions within thematrix.
In this coursework, you will implement such a sparse matrix data structure. We assume all the
elementsareintergers.Aspartof thehandoutmaterials,youarealreadygivenasourcefile
SparseMatrix.javathatprovides askeletonfor theclass SparseMatrix. The class hasdata
members for the number of matrix rows and columns:
private int numRows; private
int numCols;
In addition, the SparseMatrixclass stores non-zero elements using a dynamic array
private ArrayList< Entry > entries;
Eacharrayelement referstoaninstanceof theEntryclass,whichstoresthepositionandvalueofa
non-zero matrix element. The Entryclass is already implemented in SparseMatrix.java:
private class Entry
private int position; private int
value;
. . .
}
Herepositionisdefinedasthe(0-based)indexof thevaluewithintherow-majorfullarray
representation that includes all matrix elements. For example, for the following sparse matrix
1 0 2
0 4 0
its row-major full array representation is
{
20 0 0 0
0 30 0 40 0 0
0 0 0 0
0 0 0 0 0 80
5
(1, 0, 2, 0, 0, 0, 0, 4, 0).
Within this array there are three non-zero values:
6
• value1hasarrayindex0;
• value2hasarrayindex2;
• value 4 has array index 7.
Withintheentriesarray,theelementsarestoredinascendingorderoftheirpositionfield.
So the entriesarray looks like:
Position: 0
Value: 1
Position: 2
Value: 2
Position: 7
Value: 4
In this coursework, you will complete the sparse matrix data structure by implementing the following
functionalities.
- Loading a matrix from a file. Wewill use a text file to store the information and elements of a
sparsematrix.Thefirst rowofthefilestoresthenumberofrowsandthenumberofcolumns.Aker
that, each row stores the (0-based) row index, column index, and value for a non-zero matrix
element. fie non-zero elements can be listed in random order. For example, the text filefor
the sparse matrix in Equation (1) may look like
The following method of SparseMatrixloads a matrix from a text file: public void
loadEntries(String filename).
In SparseMatrix.java, there are already some codes inside this method to read content from the given
file. You need to complete this method, by using the read content to set up the data member entries.
Remember that the nonzero elements need to be sorted according to the positionfield. Your code for
sorting the elements should meet the following requirements:
(a) Youmust implement thesortingalgorithm by yourself and cannot use the sorting APIs
provided by Java.
(b) Yoursortingalgorithmshouldhaveworst-casetimecomplexitynohigher than O(NlogN)
whereN isthenumberofnonzeroelements.If thetimecomplexityofyour implementationis
worse than this limit, you will not get the 10% mark for its complexity.
Inaddition,youneedtocompletethefollowingmethodwhichreturnsthenumberofnon-zero
elements in the matrix:
4 6
0 0 10
1 3 40
0 1 20
3 5 80
1 1 30
7
public int numNonZeros(). - Transposingamatrix. ForamatrixM withmrowsandncolumns,itstransposeMT
isa
matrix withn rows and m columns, wherethei-throw of M is thei-th column of MT
. For
example, the transpose of the matrix in Equation (1)is
10 0 0 0
20 30 0 0
0 0 0 0
.
You need to complete the following method which returns the transpose of the current sparse
matrix:
public SparseMatrix transpose().
fie returned matrix must be independent from the current matrix, i.e., if the current
matrixischangeda@erthismethodiscalled,thereturnedmatrixmustnotbeaffected. - Adding matrix TwoMatrices. For twomatrices AandB of thesamesize, their sumC =A+B isa where each element is the sum of the corresponding elements of A and B at the same
position. For example,
10 0 0 0 0 0 10 50
0
+
0 −3 0 0 −5 0
0 27 0 40 −5 0
.
You need to complete the following method which implements this functionality:
public SparseMatrix add(SparseMatrix M).
The returned value is a new SparseMatrixinstance that is the sum of the current matrix and the
argument M.Youcanassumethetwomatricesareof thesamedimensions,sothereisnoneedto
check if theymatch.
than O(N1 +N2), where N1 and N2 are the number of non-zero elements for each operand matrix, Your algorithm for constructing the sum matrix must have worst-case time complexity no worse respectively. If the time complexity of your implementation is worse than this limit, you will not get
the 10% mark for its complexity.
fie returned matrix must be independent from both the current matrix and the matrix
M, i.e.,if eitherthe currentmatrixorthematrix M is changeda@erthismethodis called,
the returned matrix must not be affected.
When adding two matrices, it is possible that two non-zero elements at the same position within the
two matrices sum to zero. fiese ‘new’ zeros should not be stored in the sum matrix.
- Matrix-Scalar Multiplication. The multiplication of a matrix M and a scalar a results in a new
matrixMJofthesamesizeasM,whereeachelementofMJequalstothecorrespondingelementof
0 30 0 40 0
0 0 0 0 0
0 0 0 0 0
0
80
0 0 2 0 1 0
0 0 0 0 0 0
0 0 2 0 1 0
0 0 0 0 0 80
0 40 0 0
0 0 0 0
0 0 0 80
20 0 0 30 0 25 0 25 0 0
8
Σ
×
1
150
M = , v = ,
0
400
0 30 0 40 0 0 2
M multiplied by a. For example,
10 20 0 0 0 0
0 30 0 40 0 0
20 40 0 0 0 0
0 60 0 80 0 0
0 0 0 0 0 0
×2 =
0 0 0 0 0 0
You need to complete the following method which multiplies the current matrix with a scalar and
updates entriesaccording to the result.
public void multiplyBy(int scalar).
Similar totheaddmethod,anynewzerosarisingfromthemultiplicationshouldnotbe
stored in the resultmatrix. - Matrix-Vector Multiplication. For an m n matrix M and an n-dimensional vector v, their
multiplication is an m-dimensional vector f, such that it is the lament fibs computed as
n−1
fi = Mi,j ×vj
j=0
= Mi,0 × v0 + Mi,1 × v1 + . . . + Mi,n−1 × vn−1,
where Mi,j is the element of matrix M at row i and column j, and vj is the j-th element of v. For
example, if we multiply the following matrix and vector
10 20 0 0 0 0 0
then
0 0 0 0 0 0 3
0 0 0 0 0 80 4
5
20
Mv = .