Homework 3: 9/20
One of the most common operations involving a matrix is a matrixvector multiplication
operation.
Many engineering software programs will typically perform millions of matrixvector
multiplications.
Let A be an n by n matrix with entries a_{ij}, where 1 <= i <= n
and 1 <= j <= n.
Let x be a sizen vector with entries x_{j} for 1 <= j <= n.
Then the product A*x is a sizen vector whose ith entry is
a_{i1}*x_{1} +
a_{i2}*x_{2} +
a_{i3}*x_{3} + ... +
a_{in}*x_{n}.
In other words, the ith entry of A*x is simply the dot product
of the ith row of A with x.
 Add a method called product to the CRS class that takes
a vector x (stored in a 1dimensional float array) and
returns the product of the matrix stored in the CRS object with x.
The method should have the following header:
float[] product(float[] x)
You may assume that the size of x is identical to the dimensions of the
square matrix stored in the CRS object; so there is no need to
do any error checking.
Your implementation should take advantage of the fact that (i) in
CRS representation the matrix is stored row by row and (ii) the zeroes in the
matrix, which are not explicitly stored in the CRS object,
make no contribution to the matrixvector product.

To test and experiment with the product method, write a program called
CRSTester.java.
This should contain, at least, the following methods.
 A method called uncompressedProduct that takes an
n by n matrix A, stored in the standard manner in a 2dimensional
float array, and a sizen vector x and returns the product
A*x. The header for this method should be:
float[] uncompressedProduct(float[][] A, float[] x)
 A method called generateMatrix that takes a probability
p and a positive integer n and returns an n by n matrix (stored in a
2dimensional array). Each entry in the array is nonzero with probability
p. So if p = 1/100, we would expect 99% of the entries to be 0 and 1%
of the entries to be nonzero.
The exact values of the nonzero entries does not really matter; just to
keep things simple let us assume that each nonzero entry is a real number
generated at random in the range 1 through 2.
The header for this method should be:
float[][] generateMatrix(float p, int n)

A method called generateVector that takes a positive integer n
and returns a sizen vector.
You can generate the entries of the vector at random in the range 0 through
1.
The header for this method should be:
float[] generateVector(int n)
 The goal of your experiment is to compare the performance (i.e., running
time) of product and uncompressedProduct.
The general idea is that the method product needs to access
only the nonzero entries of the matrix, whereas
uncompressedProduct looks at all entries and therefore
product should be much faster than uncompressedProduct.
To perform a comparison, set p = 1/100 and generate n by n matrices
with n = 500, 600, 700, ..., 1000.
Also generate sizen vectors for the same values of n.
Use uncompressedProduct to multiply each matrix with the
corresponding vector and record the running time of
uncompressedProduct.
Then for each matrix, construct a CRS object and then use
the method product to perform the same multiplication.
Also record the running time of product.
Make a table showing the running times of product and
uncompressedProduct for the same matrixvector pairs.
How much faster (e.g., 5 times faster) is product,
relative to uncompressedProduct? As n increases, how
does the relative speed of product and uncompressedProduct
change.
Submit the files CRS.java,
CRSTester.java, CRS.readme, CRSTester.readme,
and CRS.pdf.
The pdf file should contain your experimental results and the accompanying
discussion.