Sparse Matrix Multiplication

The sparse matrix multiplication algorithm can be seen here:
http://mathforum.org/library/drmath/view/51903.html

and at stackoverflow site too
http://stackoverflow.com/questions/15693584/fast-sparse-matrix-multiplication

The key to the linear algorithm is to find all non-zero entries in one the sparse matrix and then loop through them, update the impacted entries in the final result matrix.

Here is the code: 

	public static class Pair {
	int r, c;
	public Pair(int r, int c){
	this.r = r; this.c = c;
	}
	}
	//assume A has more 0s than B, more sparse!
	public int[][] multiply(int[][] A, int[][] B) {
	//create a set store all non-zero entries in A
	Set<Pair> storeA = new HashSet<>();
	for(int r=0; r<A.length; r++){
	for(int c=0; c<A[0].length; c++){
	if(A[r][c]!=0)
	storeA.put(new Pair(r, c));
	}
	}
	//create a map to map row index in B to non-zero indices on that row
	Map<Integer, Set<Integer>> storeB = new HashMap<>();
	for(int r=0; r<B.length; r++){
	storeB.put(r, new HashSet<Integer>());
	for(int c=0; c<B[0].length; c++){
	if(B[r][c]!=0)
	storeB.get(r).add(c);
	}
	}
	int[][] result = new int[A.length][B[0].length];
	//now go through each entries in storeA to populate the entries in result which depends on it
	for(Pair p : storeA){
	for(int c2 : storeB.get(p.c)){
	result[p.r][c2] += A[p.r][p.c] * B[p.c][c2];
	}
	}
	return result;
	}

view raw SparseMatrixMultiplication.java hosted with ❤ by GitHub