311. Sparse Matrix Multiplication

Problem Description

The problem at hand requires us to perform the multiplication of two sparse matrices. A sparse matrix is a matrix that is comprised mostly of zero values. The input consists of two matrices mat1 and mat2 where mat1 is of size m x k and mat2 is of size k x n. The task is to compute the matrix product of mat1 and mat2 and return the resulting matrix. It's assumed that the multiplication of the given matrices is always valid, which means that the number of columns in mat1 is equal to the number of rows in mat2. The output should also be in the form of a sparse matrix where the spaces are optimized to store only non-zero values as much as possible.

Intuition

The intuitive approach to matrix multiplication involves three nested loops, iterating through each row of the first matrix and each column of the second matrix to calculate the values of the resulting matrix. However, since we are given a condition that these are sparse matrices, many of these calculations will involve multiplication by zero, which is unnecessary and can be skipped to save computation time and space.

The idea behind the solution approach is to preprocess each input matrix to filter out all the zero values and keep track of the non-zero values along with their positions. This preprocessing step helps to perform multiplication operations only when it is needed (i.e., only with the non-zero values).

The function f(mat) in the provided solution converts a matrix into a list of lists, where each sublist contains tuples. Each tuple has two elements: the column index and the value of the non-zero element in the matrix. This effectively compresses the matrix to store only the necessary information needed for the multiplication.

Once we have these compressed representations g1 and g2 of mat1 and mat2, respectively, we create an answer matrix ans initialized with zeros. For each row of mat1, we look at the non-zero values and their column indexes. For each of these non-zero values, we find the respective row (with matching column index) in g2 and multiply the corresponding elements. The product is then added to the correct position in the answer matrix.

This approach significantly reduces the number of multiplication operations, particularly when the matrices have a lot of zeros, which is very common in applications that deal with sparse data.

Solution Approach

The solution follows a two-step approach: preprocessing the input matrices to extract the non-zero values with their positions, and then performing a modified multiplication that only operates with these non-zero values.

Preprocessing Step

The preprocessing function f(mat) is a decisive optimization in the algorithm. It takes advantage of the matrix's sparsity to reduce the complexity of the multiplication step. The function goes through each element of the given matrix mat and records the column index and the value of all non-zero elements in a new data structure which we refer to as g.

For every row i in mat, a list g[i] is created. For every non-zero element x in row, a tuple (j, x) is appended to g[i], where j is the column index of x. This results in a list of lists where each sublist represents a row and contains only the relevant data for multiplication - that is, the column position and value of non-zero elements.

Matrix Multiplication Step

Once we have applied f to both mat1 and mat2, obtaining g1 and g2, we proceed to the actual multiplication.

1. We initialize the answer matrix ans with the correct dimensions m x n and fill it with zeros. To do this, we build a list of lists with m sublists each containing n zeros. {[0] * n for _ in range(m)} creates a list with m elements, each of which is a list of n zeros.

2. We then iterate through each row i of mat1. For each non-zero element x in this row (represented as a tuple (k, x) in g1[i]), we perform the next steps:

   • For every tuple (j, y) in g2[k], which represents the non-zero elements of the k-th row in mat2, we multiply the value x from mat1 with the value y from mat2, and accumulate the product into the appropriate cell in the answer matrix ans[i][j].

3. This accumulator step, ans[i][j] += x * y, is the core of matrix multiplication. It adds up the product of corresponding elements from pairwise aligned rows of mat1 and columns of mat2.

4. The nested loops over g1[i] and g2[k] ensure that we only consider terms that contribute to the final answer, avoiding the needless multiplication by zero which is the central inefficiency in dense matrix multiplication.

This algorithm maintains an efficient computation by only considering the relevant (non-zero) elements in the multiplication, significantly speeding it up for sparse matrices. The use of list comprehensions and tuple unpacking in Python contributes to the readability and conciseness of the code, while the use of a list of lists as a data structure allows for fast access and update of individual elements.

Example Walkthrough

Let's walk through a simple example to illustrate the solution approach. Suppose we have the following two sparse matrices mat1 and mat2.

mat1 (2x3 matrix):

1[1, 0, 0]
2[0, 0, 3]

mat2 (3x2 matrix):

1[1, 2]
2[0, 0]
3[0, 4]

The expected result of the multiplication will be a 2x2 matrix. Now, let's use the solution approach to calculate this.

Preprocessing Step

First, we preprocess mat1 and mat2 into their sparse representations g1 and g2 using function f(mat). Non-zero values and their column indices are kept.

Result of f(mat1) is g1 (list of lists of tuples):

1[
2 [(0, 1)],   // Only element in first row is `1` at column `0`
3 [(2, 3)]    // Only element in second row is `3` at column `2`
4]

Result of f(mat2) is g2 (list of lists of tuples):

1[
2 [(0, 1), (1, 2)],   // Elements are `1` at column `0` and `2` at column `1`
3 [],                 // Second row is all zeros, no non-zero elements
4 [(1, 4)]            // Only element in third row is `4` at column `1`
5]

Matrix Multiplication Step

Next, we perform the matrix multiplication:

1. Initialize the answer matrix ans filled with zeros. In this case, an 2x2 matrix would look like:

1ans = [
2 [0, 0],
3 [0, 0]
4]

2. For each row i in g1, and for each tuple (k, x) in g1[i], we do the following:

   • If i is 0 (first row in mat1), we process g1[0], which is [(0, 1)]. There's only one non-zero value 1 at column 0. We find all non-zero elements in row 0 of g2 and multiply:

     • We multiply 1 (from g1[0][0]) * 1 (from g2[0][0]) and add it to ans[0][0].
     • We multiply 1 (from g1[0][0]) * 2 (from g2[0][1]) and add it to ans[0][1].

   • If i is 1 (second row in mat1), we process g1[1], which is [(2, 3)]. There's only one non-zero value 3 at column 2. We find all non-zero elements in row 2 of g2 and multiply:

     • We multiply 3 (from g1[1][0]) * 4 (from g2[2][1]) and add it to ans[1][1].

The ans matrix now contains the result of the multiplication:

1ans = [
2 [1, 2],
3 [0, 12]
4]

This walk-through illustrates how the algorithm efficiently performs multiplication by directly accessing the non-zero elements and their positions, avoiding unnecessary multiplications with zero, which would not contribute to the result.

Solution Implementation

Time and Space Complexity

Time Complexity

To analyze time complexity, let's examine the code step by step.

1. Function f(mat): Sparse Matrix Representation - This function converts a regular matrix to a sparse representation by recording non-zero elements' coordinates and their values. If mat has dimensions r x c with t non-zero elements, then this function would take O(r * c) time, assuming the worst case where every element needs to be checked.

2. Conversion to Sparse Representation - g1 = f(mat1) is called for the first matrix having dimensions m x k (assuming m rows and k columns), and g2 = f(mat2) for the second matrix having dimensions k x n. The total time for these calls is O(m * k) + O(k * n) = O(m * k + k * n).

3. Matrix Multiplication - The nested loops for matrix multiplication iterate over m rows of mat1, k sparse columns of mat1, and n sparse columns of mat2. The number of iterations would be dependent on the number of non-zero elements in the sparse representations of mat1 and mat2. If nz1 and nz2 are the number of non-zero entries in mat1 and mat2 respectively, the time complexity for the multiplication part is O(nz1 * n) + O(nz2) because for every non-zero element in g1[i], we need to iterate over potentially up to n elements in g2[k]. However, in a truly sparse scenario, not every element in g2[k] correlates to a non-zero product, so this is an upper bound.

The overall time complexity would be O(m * k + k * n + nz1 * n + nz2) which is typically represented as O(m * k + k * n) if we are looking at worst-case scenario considering dense matrices, where nz1 approaches m * k and nz2 approaches k * n.

Space Complexity

For space complexity, we have:

1. Sparse Representation - Storing the sparse representation of both matrices, which might take up to O(m * k + k * n) space in the worst case (each original matrix is dense), but in practice would be O(nz1 + nz2) for sparse matrices with nz1 and nz2 non-zero entries respectively.

2. Output Matrix ans - Initializing a result matrix of dimensions m x n, thus requiring space complexity of O(m * n).

The space complexity is dominated by the larger of the two factors: output matrix and sparse representations. Therefore, the space complexity is O(m * n + nz1 + nz2). In worst-case scenario with dense matrices, this would simplify to O(m * n).

Learn more about how to find time and space complexity quickly using problem constraints.