Sparse Matrix Multiplication

Question (LC.311)

Given two sparse matrices A and B, find A x B.

Example

I: A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

B = [
  [7, 0, 0],
  [0, 0, 0],
  [0, 0, 1]
]

O: Y = [
  [ 7, 0, 0],
  [-7, 0, 3]
]

Analysis

We come up the brute force algorithm pretty easily by following the matrix multiplication rule. To compute $Y_{ij}$, we need to multiply elements in ith row from A and jth column from B and sum them up.

Code

public int[][] multiply(int[][] A, int[][] B) {
    int a = A.length, b = A[0].length;
    int c = B.length, d = B[0].length;
    if (b != c) {
        return null;
    }
    // A x B = P
    int[][] P = new int[a][d];
    // P_ij
    for (int i = 0; i < a; i++) {
        for (int j = 0; j < d; j++) {
            int p_ij =  0;
            for (int k = 0; k < b; k++) {
                // if (A[i][k] == 0 || B[k][j] == 0) continue;
                p_ij += A[i][k] * B[k][j];
            }
            P[i][j] = p_ij;
        }
    }
    return P;
}

The brute force solution only beats 4% of the solutions. But by adding the check for 0 element, it beats 60% of the solution.

Reference

• Wikipedia - Sparse Matrix

• Paper - Fast Sparse Matrix Multiplication