Parts A is required. Part B is optional and is worth four points extra credit (but must be submitted in addition to, and along with, Part A).
Part A (required) – A Simple Array Implementation for Large Matrices
We already know how to allocate and work with 2-D arrays (matrices) from our CS 1B (CIS 27B) class. For example, here we allocate two double matrices:
// non-sparse matrices double[][] mat, matAns; mat = new double[MAT_SIZE][MAT_SIZE]; matAns = new double[MAT_SIZE][MAT_SIZE];
Look up matrix multiplication on the web or in a math book. It is a very simple and short formula, but it’s good for you to find on your own. Create a static method in your main class that takes two input matrices, and the third a return (reference) product matrix:
public static void matMult( double[][] matA, double[][] matB, double[][] matC)
To keep things simple, we’ll assume all matrices are square, but we should check that the first rows of each matrix are the same size. If they are, we’ll assume all is well (and let Java throw exceptions if the client passed bad matrices). After reading the definition of matrix multiplication, but before implementing it, determine, using the tools you have learned, the time complexity of this operation relative to M. You should be able to get both a tight O() upper bound as well as a Θ() estimate for multiplying two MxM matrices together. Put this into writing to be handed in, along with your reasoning at the bottom of your assignment. Next, write the function for matMult(). Also, for comparison, write a display method for these dynamic matrices like you did for sparse matrices last week: one that shows a square sub-matrix of size = size anchored at position (start, start):
public static void matShow(double[][] matA, int start, int size
This week we’re making it a static function, so it must take the matrix as a parameter.
Now that we have our tools, we can time matrix multiplication (and examine small portions of the answers). Our game will be to generate a semi-sparse matrix (between 1% and 25% of the size of the matrix, non-zero) and then “square” the matrix (multiply it by itself) using matrix multiplication. We’ll show a small 10×10 square sub-portion of the matrix, and then that same portion of the squared matrix.
Here is the idea of a test main():
//——————————————————public class Foothill{ final static int MAT_SIZE = 400; // ——- proof of correctness ————– public static void main(String[] args) throws Exception { int r, randRow, randCol; long startTime, stopTime; double randFrac; double smallPercent; NumberFormat tidy = NumberFormat.getInstance(Locale.US); tidy.setMaximumFractionDigits(4); // non-sparse matrices double[][] mat, matAns; // allocate matrices // ?? // generate small% of non-default values bet 0 and 1 smallPercent = MAT_SIZE/10. * MAT_SIZE; for (r = 0; r < smallPercent; r++) { // ?? } // 10x10 submatrix in lower right matShow(mat, MAT_SIZE - 10, 10); startTime = System.nanoTime(); matMult(mat, mat, matAns); stopTime = System.nanoTime(); matShow(matAns, MAT_SIZE - 10, 10); System.out.println("nSize = " + MAT_SIZE + " Mat. Mult. Elapsed Time: " + tidy.format( (stopTime - startTime) / 1e9) + " seconds."); } ...} Start out with a small M like 50 or 100. Then, when everything is working, time your algorithm. Some questions you should answer (required): What was the smallest M that gave you a non-zero time? What happened when you doubled M, tripled it, quadrupled it, etc? Give several M values and their times in a table. How large an M can you use before the program refuses to run (exception or run-time error due to memory overload) or it takes so long you can't wait for the run? How did the data agree or disagree with your original time complexity estimate? Here is part of two possible runs: 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.000.00 0.00 0.01 0.00 0.00 0.00 0.00 0.00 0.00 0.000.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.000.00 0.00 0.00 0.66 0.00 0.00 0.00 0.00 0.00 0.000.00 0.95 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.000.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.000.00 0.00 0.00 0.00 0.00 0.00 0.50 0.00 0.00 0.000.00 0.00 0.00 0.96 0.00 0.00 0.00 0.00 0.00 0.000.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.000.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.000.00 0.00 0.00 0.00 0.00 0.09 0.00 0.00 0.00 0.000.00 0.00 0.00 0.00 0.00 0.12 0.00 0.00 0.00 0.000.00 0.00 0.00 0.00 0.00 0.00 0.05 0.00 0.00 0.000.00 0.00 0.00 0.44 0.00 0.53 0.00 0.00 0.00 0.000.00 0.00 0.02 0.00 0.02 0.00 0.00 0.00 0.71 0.000.02 0.00 0.00 0.25 0.00 0.00 0.00 0.00 0.00 0.000.00 0.00 0.76 0.82 0.00 0.58 1.26 0.47 0.00 0.000.00 0.00 0.00 1.14 0.00 0.00 0.00 0.00 0.00 0.000.00 0.00 0.38 0.00 0.42 0.25 0.45 0.00 0.00 0.000.35 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00Size = 100 Mat. Mult. Elapsed Time: 0.0072 seconds.0.45 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.000.42 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.000.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.000.00 0.00 0.61 0.00 0.00 0.00 0.00 0.00 0.00 0.000.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.000.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.000.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.09 0.000.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.000.00 0.00 0.00 0.00 0.00 0.00 0.63 0.00 0.00 0.000.58 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.000.42 0.41 0.00 0.00 0.07 0.00 0.71 0.00 0.21 0.000.19 0.00 0.80 0.49 0.00 0.00 0.00 0.34 0.00 1.550.35 0.55 0.00 0.00 0.00 0.00 0.00 0.27 0.01 0.000.00 0.00 0.00 0.00 0.60 0.00 0.00 0.00 0.00 0.180.00 0.24 0.33 0.13 0.10 0.00 0.00 0.00 0.35 0.380.00 0.00 0.45 0.77 0.00 0.44 0.00 0.00 0.09 0.000.00 0.03 0.01 0.13 0.00 0.09 0.06 0.00 0.38 0.080.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.07 0.000.00 1.35 0.33 0.00 0.00 0.45 0.00 0.00 0.37 0.000.26 0.17 0.00 0.77 0.10 0.00 0.00 0.00 0.00 0.00Size = 200 Mat. Mult. Elapsed Time: 0.0446 seconds. You should show at least one multiplication to demonstrate that you are getting good values. After that, you can run the program without showing the matrices – only the times. Part B (4 points extra credit) – A Sparse Matrix Implementation for Large Matrices Derive a class from last week's SparseMat that adds a matMult() method. You can make your class tied to the type Double. public boolean matMult(SparseMatWMult matA, SparseMatWMult matB)class SparseMatWMult extends SparseMat{ // constructor ?? // multiply: public boolean matMult(SparseMatWMult matA, SparseMatWMult matB) { // ?? }}
matMult() sets the this object to the product of the passed parameters – note: as usual it must not do any output. It does full error testing for dimension compatibility, and insists that the matrices all have sizes 1×1 or larger. It returns false if any of this fails. Otherwise, it does the multiplication and returns true.
Take care:

Don’t try to translate the no-brainer version of matrix multiplication done in Part A into sparse matrix set() and get() terminology. It won’t work: you will be waiting two days for a small 1000×1000 matrix multiply if you do. You have to use your head and look at the list structure, only doing what you need to do. Really streamline this. Assume that you have a sparse matrix, which means that only a few elements per row will be non-zero. Be as smart as you can, because you’ll need to really press down on the times. Although sparse matrices allow large structures to be stored, they are also slower due to the overhead of linked lists, array lists, etc.
In your loops, compute what you can outside so that you are not re-evaluating things which evaluate to the same number each loop pass.
You’ll need to clear out the this object and resize it to hold the result. This has to be done early, before you go into the multiplication loops.
It’s okay to use temporary variables to make things clear, even in the loops. They won’t add much time. So don’t try to save time by smashing a lot of code or computation onto a couple lines. This won’t help. You need to save time by avoiding doing computations in loops.
Test your multiply on the following 5×5 matrices to make sure that your algorithm is working:

First Matrix, n: 1.0 2.0 3.0 4.0 5.0-1.0 -2.0 -3.0 -4.0 -5.0 1.0 3.0 1.0 3.0 1.0 0.0 1.0 0.0 1.0 0.0-1.0 -1.0 -1.0 -1.0 -1.0Second Matrix, m: 2.0 1.0 5.0 0.0 2.0 1.0 4.0 3.0 2.0 7.0 4.0 4.0 4.0 4.0 4.0 7.0 1.0 -1.0 -1.0 -1.0 0.0 0.0 8.0 -1.0 -6.0Product Matrix, n x m:44.0 25.0 59.0 7.0 -6.0-44.0 -25.0 -59.0 -7.0 6.030.0 20.0 23.0 6.0 18.0 8.0 5.0 2.0 1.0 6.0-14.0 -10.0 -19.0 -4.0 -6.0
Once you get this working, start over and use small matrices, again timing things.

Are the times longer or shorter than for dynamic matrices?
Are the growth rates larger or smaller? By how much?
Create a table and answer the same questions as before.
What was the largest M you could use here, and was the reason the same or different than for dynamic arrays?
Try different sparseness values: 1% 5% 10% 0.2%, and report how the growth rates behave in each case.

In order to get credit for option B you must supply a proof of correctness run similar to above and demonstrate runs for 1% sparse square matrices with row and col sizes up through 800, 1600 and 3200. The 800 x 800 must run in less than 1 second and 3200 x 3200 must run in less than 5 minutes.