Sparse Matrix Multiplication (Java)

Spread the love

Given two sparse matrices A and B, return the result of AB.

You may assume that A’s column number is equal to B’s row number.

1. Naive Method

We can implement Sum(A_ik * B_kj) -> C_ij as a naive solution.

public int[][] multiply(int[][] A, int[][] B) {
    //validity check
 
    int[][] C = new int[A.length][B[0].length];
 
    for(int i=0; i<C.length; i++){
        for(int j=0; j<C[0].length; j++){
            int sum=0;
            for(int k=0; k<A[0].length; k++){
                sum += A[i][k]*B[k][j];
            }
            C[i][j] = sum;
        }
    }
 
    return C;
}

Time complexity is O(n^3).

2. Optimized Method

From the formula: Sum(A_ik * B_kj) -> C_ij

We can see that when A_ik is 0, there is no need to compute B_kj. So we switch the inner two loops and add a 0-checking condition.

public int[][] multiply(int[][] A, int[][] B) {
    //validity check
 
    int[][] C = new int[A.length][B[0].length];
 
    for(int i=0; i<C.length; i++){
        for(int k=0; k<A[0].length; k++){
            if(A[i][k]!=0){
                for(int j=0; j<C[0].length; j++){
                    C[i][j] += A[i][k]*B[k][j];
                }
            }
        }
    }
 
    return C;
}

Since the matrix is sparse, the time complexity is ~O(n^2) which is much faster than O(n^3).

Tags: ,