Solution For Sparse Matrix Multiplication

Problem:

Given two sparse matrices A and B, return their product.

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

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

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

Output:
| 1 0 0 | | 7 0 0 | | 7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
| 0 0 1 |

Solution:

Approach:
The first intuition that comes in mind for multiplication of matrices is the brute force method that is to take two for loops of rows and columns and then inner loop for calculating the product of the elements and then taking sum of them. But, the complexity of this method is O(n^3).

To improve the time complexity of the program, we can consider the approach of sparse matrix.

Sparse matrix is in which the number of non-zero elements is fewer than the number of zero elements. Therefore, to reduce the time of multiplication we can skip the multiplication of zero and use the non-zero numbers to compute the result.

Now, let’s dive into the steps of this algorithm:

Algorithm:
1. Define a function sparse_multiplication() that will take two sparse matrices as input, A and B.
2. Extract the row and column of A and B for easy use later.
3. Define an empty list, result, to store the product of matrices.
4. Define a helper function, dot_product(), that will return the dot product of two lists, row and col, which we will use to calculate the product.
5. Create a dictionary, nzA, to store non-zero elements of matrix A with their row and column numbers.
6. Loop for row in range(rowA) and colB in range(colB) to iterate through the rows of A and columns of B.
7. Define an empty list col for later use.
8. For i in nzA.keys(), check if colB equal to the column of i in matrix B.
9. If it is true, append the value of i to col list.
10. Call dot_product() with two parameters nzA[i] and B[c].
11. Append the result of dot_product() to the corresponding element in result.
12. Return the result in the format of a list of lists.

Code:
def sparse_multiplication(A, B):
rowA, colA = len(A), len(A[0])
rowB, colB = len(B), len(B[0])
result = [[0] * colB for _ in range(rowA)]

def dot_product(row, col):
    return sum([row[i] * col[i] for i in range(len(row))])

nzA = {}
for row in range(rowA):
    nzA[row] = {}
    for col in range(colA):
        if A[row][col] != 0:
            nzA[row][col] = A[row][col]

for row in range(rowA):
    for colB in range(colB):
        col = []
        for i in nzA[row].keys():
            if colB == i: col.append(nzA[row][i])
        result[row][colB] = dot_product(col, [x[colB] for x in B])

return result

Time Complexity: The time complexity of this algorithm is O(n^2) as we are looping through the rows of A and the columns of B.

Space Complexity: The space complexity of this algorithm is also O(n^2) because we are creating a dictionary and a list of lists to store values.

Conclusion:
In this article, we learned about the sparse matrix multiplication problem, a method to solve the problem using dictionaries and lists, and the time and space complexity of the algorithm.

Step by Step Implementation For Sparse Matrix Multiplication

class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int m = A.length, n = A[0].length, nB = B[0].length;
        int[][] C = new int[m][nB];

        for(int i = 0; i < m; i++) {
            for(int k = 0; k < n; k++) {
                if (A[i][k] != 0) {
                    for (int j = 0; j < nB; j++) {
                        if (B[k][j] != 0) C[i][j] += A[i][k] * B[k][j];
                    }
                }
            }
        }
        return C;
    }
}

def sparseMatrixMultiplication(A, B):

    # check if the number of columns in A is equal to the number of rows in B
    if len(A[0]) != len(B):
        return None

    # initialize the result matrix
    result = [[0 for i in range(len(B[0]))] for j in range(len(A))]

    # go through each row of A
    for i in range(len(A)):
        # go through each column of B
        for j in range(len(B[0])):
            # go through each element in the ith row of A and the jth column of B
            for k in range(len(B)):
                result[i][j] += A[i][k] * B[k][j]

    return result

// given two sparse matrices A and B, return their multiplication C = AB

// A and B are given as arrays of sparse matrices, with each element representing a row of the matrix

// C will be an array of sparse matrices, with each element representing a row of the matrix

var sparseMatrixMultiplication = function(A, B) {
    
    // we assume that A and B are both arrays of sparse matrices
    
    var C = [];
    
    for (var i = 0; i < A.length; i++) {
        var row = A[i];
        var newRow = [];
        
        for (var j = 0; j < B.length; j++) {
            var element = row[j];
            
            // if the element is non-zero, we need to multiply it by every element in column j of matrix B
            if (element !== 0) {
                var column = B[j];
                
                for (var k = 0; k < column.length; k++) {
                    var columnElement = column[k];
                    
                    // if the column element is non-zero, we need to multiply it by the element from matrix A
                    if (columnElement !== 0) {
                        // if this is the first time we've seen this element in the new row, we need to initialize it to 0
                        if (newRow[k] === undefined) {
                            newRow[k] = 0;
                        }
                        
                        // multiply the two elements and add them to the new row
                        newRow[k] += element * columnElement;
                    }
                }
            }
        }
        
        // add the new row to the result matrix
        C.push(newRow);
    }
    
    return C;
};

vector> multiply(vector>& A, vector>& B) {
    int m = A.size(), n = A[0].size(), nB = B[0].size();
    vector> C(m, vector(nB, 0));
    for (int i = 0; i < m; ++i) {
        for (int k = 0; k < n; ++k) {
            if (A[i][k]) {
                for (int j = 0; j < nB; ++j) {
                    if (B[k][j]) C[i][j] += A[i][k] * B[k][j];
                }
            }
        }
    }
    return C;
}

public class Solution {
    public int[][] Multiply(int[][] A, int[][] B) {
        int m = A.Length, n = A[0].Length, nB = B[0].Length;
        int[][] C = new int[m][];
        for(int i = 0; i < m; i++) {
            C[i] = new int[nB];
        }
        
        for(int i = 0; i < m; i++) {
            for(int k = 0; k < n; k++) {
                if (A[i][k] != 0) {
                    for (int j = 0; j < nB; j++) {
                        if (B[k][j] != 0) C[i][j] += A[i][k] * B[k][j];
                    }
                }
            }
        }
        return C;
    }
}