Main.java

import java.text.NumberFormat;
import java.util.Locale;

//------------------------------------------------------
public class Main {
   final static int MAT_SIZE = 50;

   // ------- proof of correctness --------------
   public static void main(String[] args) throws Exception {
      int r, randRow, randCol;
      long startTime = 0, stopTime = 0;
      double randFrac;
      double smallPercent;
      NumberFormat tidy = NumberFormat.getInstance(Locale.US);
      tidy.setMaximumFractionDigits(4);

      // testing matrix
      double[][] mat = new double[][] { { 0, 0, 0, 1, 2 }, { 0, 1, 3, 0, 1 },
            { 0, 0, 5, 2, 0 }, { 0, 1, 0, 1, 0 }, { 0, 0, 1, 2, 3 } };
      double[][] matAns = new double[5][5];
      SparseMatMult mat1 = new SparseMatMult(MAT_SIZE, MAT_SIZE, 0.);
      System.out
            .println("-----Testing to see matrix multiplication is correct----");

      showBeforeAndAfter(mat, matAns, 0, 5);

      System.out.println("Result successful - try 10x10 random next");

      mat = new double[10][10];
      matAns = new double[10][10];
      loadUpMatrices(10, mat);
      showBeforeAndAfter(mat, matAns, 0, 10);
      SparseMatMult sparseMatAns = new SparseMatMult(MAT_SIZE, MAT_SIZE, 0.);
      TenPercentSparseTest();
      NXMTest();
      System.out
            .println("----------size testing for normal matrices--------------");
      System.out
            .println("-------(Sparsity doesn't matter for normal matrix)-------");
      for (int i = 50; i < 1000; i = i * 2) {
         testMatrix(i);
      }

      System.out.println("----------Sparse matrix testing----------");
      System.out.println("----------sparsity 1% testing-------------");
      for (int i = 50; i < 4000; i = i * 2) {
         mat1 = new SparseMatMult(i, i, 0.);
         testSparseMatrix(i, 100.);
      }
      System.out.println("----------sparsity 5% testing-------------");
      for (int i = 50; i < 2000; i = i * 2) {
         testSparseMatrix(i, 20.);
      }
      System.out.println("----------sparsity .5% testing-------------");
      for (int i = 50; i < 2000; i = i * 2) {
         testSparseMatrix(i, 200.);
      }
      System.out.println("----------sparsity 2.5% testing-------------");
      for (int i = 50; i < 2000; i = i * 2) {
         testSparseMatrix(i, 40.);
      }
   }

   public static void loadUpMatrices(int size, double sparsity,
         SparseMatMult mat1) {
      double smallPercent = (double) size / sparsity * size;
      for (int r = 0; r < smallPercent; r++) {
         int rowInd = (int) (Math.random() * size);
         int colInd = (int) (Math.random() * size);
         double randVal = Math.random();
         mat1.set(rowInd, colInd, randVal);
      }
      // mat1.reformatMatrices();
   }

   public static void loadUpMatrices(int size, double[][] mat1) {
      double smallPercent = size * size;
      for (int r = 0; r < smallPercent; r++) {
         int rowInd = (int) (Math.random() * size);
         int colInd = (int) (Math.random() * size);
         double randVal = Math.random();
         mat1[rowInd][colInd] = randVal;
      }
   }

   public static void testSparseMatrix(int size, double sparsity) {
      long startTime, stopTime;
      NumberFormat tidy = NumberFormat.getInstance(Locale.US);
      tidy.setMaximumFractionDigits(4);
      SparseMatMult mat1 = new SparseMatMult(size, size, 0.);
      SparseMatMult sparseMatAns = new SparseMatMult(size, size, 0.);
      loadUpMatrices(size, sparsity, mat1);
      startTime = System.nanoTime();
      sparseMatAns.matMult(mat1, mat1);
      stopTime = System.nanoTime();

      System.out.println("\nSize = " + size
            + " Sparse Mat. Mult. Elapsed Time: "
            + tidy.format((stopTime - startTime) / 1e9) + " seconds.");
   }

   public static void testMatrix(int size) {
      double[][] mat = new double[size][size];
      double[][] matAns = new double[size][size];
      long startTime, stopTime;
      NumberFormat tidy = NumberFormat.getInstance(Locale.US);
      tidy.setMaximumFractionDigits(4);
      loadUpMatrices(size, mat);
      startTime = System.nanoTime();
      MatrixMultiplication.matMult(mat, mat, matAns);
      stopTime = System.nanoTime();

      System.out.println("\nSize = " + size + " Mat. Mult. Elapsed Time: "
            + tidy.format((stopTime - startTime) / 1e9) + " seconds.");
   }

   public static void showBeforeAndAfter(double[][] mat, double[][] matAns,
         int start, int end) {
      long startTime, stopTime;
      NumberFormat tidy = NumberFormat.getInstance(Locale.US);
      tidy.setMaximumFractionDigits(4);
      MatrixMultiplication.matShow(mat, start, end);
      System.out.println();
      startTime = System.nanoTime();
      MatrixMultiplication.matMult(mat, mat, matAns);
      stopTime = System.nanoTime();
      MatrixMultiplication.matShow(matAns, start, end);
   }

   public static void NXMTest() {
      System.out.println("-----Testing NxM matrix for sparse matrices-----");
      System.out.println("-----normal matrix attempt-----");
      double[][] matrixN = { { 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.0 } };
      double[][] matrixM = { { 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.0 } };
      double[][] matAns = new double[5][5];
      MatrixMultiplication.matShow(matrixN, 0, 5);
      System.out.println();
      MatrixMultiplication.matMult(matrixN, matrixM, matAns);
      MatrixMultiplication.matShow(matAns, 0, 5);
      System.out.println("-----sparse matrix attempt-----");
      // same matrix
      SparseMatMult matN = new SparseMatMult(5, 5, 0.);
      for (int i = 0; i < 5; i++) {
         matN.set(0, i, (double) (i + 1));
         matN.set(1, i, (double) (-1 * (i + 1)));
         matN.set(4, i, -1.);
      }
      for (int i = 0; i < 5; i++) {
         if (i % 2 == 1) {
            matN.set(2, i, 3.);
            matN.set(3, i, 1.);
         } else {
            matN.set(2, i, 1.);
         }
      }
      matN.showSubSquare(0, 5);
      // matN.reformatMatrices();
      SparseMatMult matM = new SparseMatMult(5, 5, 0.);
      testingNMMethod(matM);
      // matM.reformatMatrices();
      SparseMatMult matAnswer = new SparseMatMult(5, 5, 0.);
      matAnswer.matMult(matN, matM);
      matAnswer.showSubSquare(0, 5);
   }

   public static void TenPercentSparseTest() {
      long startTime, stopTime;
      NumberFormat tidy = NumberFormat.getInstance(Locale.US);
      tidy.setMaximumFractionDigits(4);
      System.out
            .println("----------10% sparse(Proof extra credit same result)-------");
      System.out.println("---normal matrix attempt---");

      double[][] mat = new double[MAT_SIZE][MAT_SIZE];
      double[][] matAns = new double[MAT_SIZE][MAT_SIZE];
      SparseMatMult mat1 = new SparseMatMult(MAT_SIZE, MAT_SIZE, 0.);

      double smallPercent = MAT_SIZE / 10. * MAT_SIZE;
      for (int r = 0; r < smallPercent; r++) {
         int rowInd = (int) (Math.random() * MAT_SIZE);
         int colInd = (int) (Math.random() * MAT_SIZE);
         double randVal = Math.random();
         // including both matrices and associating with same values
         // allows for testing to check for similarities here
         mat[rowInd][colInd] = randVal;
         mat1.set(rowInd, colInd, randVal);
      }

      // 10x10 submatrix in lower right
      showBeforeAndAfter(mat, matAns, MAT_SIZE - 10, 10);

      System.out.println("---sparse matrix attempt---");
      mat1.showSubSquare(MAT_SIZE - 10, 10);
      // mat1.reformatMatrices();
      System.out.println();
      SparseMatMult sparseMatAns = new SparseMatMult(MAT_SIZE, MAT_SIZE, 0.);
      startTime = System.nanoTime();
      sparseMatAns.matMult(mat1, mat1);
      stopTime = System.nanoTime();

      sparseMatAns.showSubSquare(MAT_SIZE - 10, 10);

      System.out.println("\nSize = " + MAT_SIZE
            + " Sparse Mat. Mult. Elapsed Time: "
            + tidy.format((stopTime - startTime) / 1e9) + " seconds.");
   }

   public static void testingNMMethod(SparseMatMult mat) {
      mat.set(0, 0, 2.0);
      mat.set(0, 1, 1.0);
      mat.set(0, 2, 5.0);
      mat.set(0, 3, 0.0);
      mat.set(0, 4, 2.0);
      mat.set(1, 0, 1.0);
      mat.set(1, 1, 4.0);
      mat.set(1, 2, 3.0);
      mat.set(1, 3, 2.0);
      mat.set(1, 4, 7.0);
      mat.set(2, 0, 4.0);
      mat.set(2, 1, 4.0);
      mat.set(2, 2, 4.0);
      mat.set(2, 3, 4.0);
      mat.set(2, 4, 4.0);
      mat.set(3, 0, 7.0);
      mat.set(3, 1, 1.0);
      mat.set(3, 2, -1.0);
      mat.set(3, 3, -1.0);
      mat.set(3, 4, -1.0);
      mat.set(4, 0, 0.0);
      mat.set(4, 1, 0.0);
      mat.set(4, 2, 8.0);
      mat.set(4, 3, -1.0);
      mat.set(4, 4, -6.0);
   }
}

MatrixMultiplication.java

public class MatrixMultiplication {
   // Multiplies two matrices and fills in matC's reference as the result
   public static void matMult(double[][] matA, double[][] matB, double[][] matC)
         throws IndexOutOfBoundsException {
      if (!validate(matA, matB, matC)) {
         throw new IndexOutOfBoundsException();
      }
      for (int i = 0; i < matA.length; i++) {
         for (int j = 0; j < matB[i].length; j++) {
            double dotProduct = 0;
            for (int k = 0; k < matA[i].length; k++) {
               // 1st mat's column x 2nd mat's row = dot product
               dotProduct += matA[i][k] * matB[k][j];
            }
            matC[i][j] = dotProduct;
         }
      }
   }

   public static void matShow(double[][] matA, int start, int size) {
      for (int i = start; (i < start + size && i < matA.length); i++) {
         for (int j = start; (j < start + size && j < matA[i].length); j++) {
            System.out.printf("%7.1f", matA[i][j]);
         }
         System.out.println();
      }
   }

   // even though the module states assumed equal sized, square matrices
   // want to make this class usable for all sizes
   public static boolean validate(double[][] matA, double[][] matB,
         double[][] matC) {
      // For the reason that col of #1 = row of #2
      if (matA[0].length != matB.length) {
         return false;
      }
      // For the reason that matC does not have sufficient capacity
      else if ((matA[0].length > matC.length || matB.length > matC[0].length)) {
         return false;
      } else
         return true;
   }
}

SparseMat.java

import java.util.ListIterator;

import cs_1c.FHarrayList;
import cs_1c.FHlinkedList;

//--------------- Class SparseMat Definition ---------------
class SparseMat<E> implements Cloneable
{
   // protected enables us to safely make col/data public
   protected class MatNode implements Cloneable
   {
      public int col;
      public E data;
      
      // we need a default constructor for lists
      MatNode()
      {
         col = 0;
         data = null;
      }

      MatNode(int cl, E dt)
      {
         col = cl;
         data = dt;
      }
      
      public Object clone() throws CloneNotSupportedException
      {
         // shallow copy
         MatNode newObject = (MatNode)super.clone();
         return (Object) newObject;
      }
   };
   
   protected int rowSize, colSize;
   protected E defaultVal;
   protected FHarrayList < FHlinkedList< MatNode > > rows;
   
   public int getRowSize() { return rowSize; }
   public int getColSize() { return colSize; }
   
   // constructor creates an empty Sublist (no indices)
   public SparseMat( int numRows, int numCols, E defaultVal)
   {
      if ( numRows < 1 || numCols < 1 )
         throw new IllegalArgumentException();
      
      rowSize = numRows;
      colSize = numCols;
      allocateEmptyMatrix();
      this.defaultVal = defaultVal;
   }
   
   protected void allocateEmptyMatrix()
   {
      int r;
      rows = new FHarrayList < FHlinkedList< MatNode > >();
      for (r = 0; r < rowSize; r++)
         rows.add( new FHlinkedList< MatNode >());   // add a blank row
   }
   
   public void clear()
   {
      int r;

      for (r = 0; r < rowSize; r++)
         rows.get(r).clear();
   }
   
   // optional method - good practice for java programmers
   public Object clone() throws CloneNotSupportedException
   {
      int r;
      ListIterator<MatNode> iter;
      FHlinkedList < MatNode > newRow;
      
      // shallow copy
      SparseMat<E> newObject = (SparseMat<E>)super.clone();
      
      // create all new lists for the new object
      newObject.allocateEmptyMatrix();
     
      // clone
      for (r = 0; r < rowSize; r++)
      {
         newRow = newObject.rows.get(r);
         // iterate along the row, looking for column c
         for (
               iter =
                  (ListIterator<MatNode>)rows.get(r).listIterator();
            iter.hasNext(); )
         {
            newRow.add( (MatNode) iter.next().clone() );
         }
      }
      
      return newObject;
   }
   
   protected boolean valid(int r, int c)
   {
      if (r >= 0 && r < rowSize && c >= 0 && c < colSize)
         return true;
      return false;
   }
   
   public boolean set(int r, int c, E x)
   {
      if (!valid(r, c))
         return false;

      ListIterator<MatNode> iter;

      // iterate along the row, looking for column c
      for (iter =
         (ListIterator<MatNode>)rows.get(r).listIterator();
         iter.hasNext(); )
      {
         if ( iter.next().col == c )
         {
            if ( x.equals(defaultVal) )
               iter.remove();
            else
               iter.previous().data = x;
            return true;
         }
      }

      // not found
      if ( !x.equals(defaultVal) )
         rows.get(r).add( new MatNode(c, x) );
      return true;
   }
   
   public E get(int r, int c)
   {
      if (!valid(r, c))
         throw new IndexOutOfBoundsException();

      ListIterator<MatNode> iter;

      // iterate along the row, looking for column c
      for (iter =
         (ListIterator<MatNode>)rows.get(r).listIterator();
         iter.hasNext(); )
      {
         if ( iter.next().col == c )
            return iter.previous().data;
      }
      // not found
      return defaultVal;
   }
   
   public void showSubSquare(int start, int size)
   {
      int r, c;

      if (start < 0 || size < 0
         || start + size > rowSize
         || start + size > colSize )
         return;

      for (r = start; r < start + size; r++)
      {
         for (c = start; c < start + size; c++)
            System.out.print( String.format("%4.1f", (Double)get(r, c)) + " " );
         System.out.println();
      }
      System.out.println();
   }
}

SparseMatMult.java

import java.util.ArrayList;
import java.util.ListIterator;

import cs_1c.FHlinkedList;

class SparseMatMult extends SparseMat<Double> {
   // coordinate storage variables
//   public ArrayList<Double> mVals;
//   public ArrayList<Integer> mRows;
//   public ArrayList<Integer> mCols;

   public SparseMatMult(int row, int col, Double defaultVal) {
      super(row, col, defaultVal);
   }

   // multiply two sparsemats and merge them into this class's sparseMat
   public boolean matMult(SparseMatMult matA, SparseMatMult matB) {
      if (matA.getColSize() != matB.getRowSize()) {
         return false;
      }

      for(int i = 0; i < matA.rows.size(); i++){
         FHlinkedList<MatNode> list = matA.rows.get(i);
         for(ListIterator<MatNode> iterate = matA.rows.get(i).listIterator(); iterate.hasNext();){
            MatNode node = iterate.next();
            for(int j = 0; j < matB.getColSize(); j++)
            if(matB.get(node.col, j) != matB.defaultVal){
               set(i, j, (get(i,j) + matB.get(node.col, j) * node.data));
            }
         }
      }
      return true;
   }

}