Sparse Matrix Multiplication
Medium · Arrays & Hashing · Explanation and code example
Yale Format
How it works
The Yale format (also known as Compressed Sparse Row/Column) is a standard way to represent sparse matrices efficiently. It uses three arrays: values (non-zero elements), column/row indices, and row/column pointers that mark where each row/column starts in the values array. By compressing mat1 row-wise and mat2 column-wise, we can efficiently compute dot products by merging two sorted lists of indices.
Steps
- Compress
mat1using Compressed Sparse Row (CSR) format: store values, column indices, and row pointers. - Compress
mat2using Compressed Sparse Column (CSC) format: store values, row indices, and column pointers. - For each cell
(row, col)in the result matrix, find the range of non-zero elements inmat1's row andmat2's column. - Use a two-pointer technique to merge these ranges: when column index in
mat1matches row index inmat2, multiply the values and add to the result. - Return the result matrix.
Complexity
- Time complexity:
O(m × n × k) - Space complexity:
O(m × k + k × n)
Where
mandkrepresent the number of rows and columns inmat1, respectively andkandnrepresent the number of rows and columns inmat2, respectively.
Things to watch for
Not Skipping Zero Elements in the First Matrix
The main optimization for sparse matrices is to skip multiplications when an element in mat1 is zero. Checking only for zeros in mat2 or not checking at all results in unnecessary computations and misses the performance benefit of sparse matrix multiplication.
Confusing Row and Column Indices During Multiplication
In matrix multiplication, element mat1[i][k] multiplies with mat2[k][j] to contribute to result[i][j]. Mixing up the shared index k or the result indices i and j leads to incorrect results.
Initializing the Result Matrix Incorrectly
The result matrix must be initialized with zeros and have dimensions m x n where m is the number of rows in mat1 and n is the number of columns in mat2. Using wrong dimensions or forgetting to initialize with zeros causes index errors or incorrect sums.
Python code example
from typing import List
class SparseMatrix:
def __init__(self, matrix: List[List[int]], col_wise: bool):
self.values, self.row_index, self.col_index = self.compress_matrix(matrix, col_wise)
def compress_matrix(self, matrix: List[List[int]], col_wise: bool):
return self.compress_col_wise(matrix) if col_wise else self.compress_row_wise(matrix)
# Compressed Sparse Row
def compress_row_wise(self, matrix: List[List[int]]):
values = []
row_index = [0]
col_index = []
for row in range(len(matrix)):
for col in range(len(matrix[0])):
if matrix[row][col]:
values.append(matrix[row][col])
col_index.append(col)
row_index.append(len(values))
return values, row_index, col_index
# Compressed Sparse Column
def compress_col_wise(self, matrix: List[List[int]]):
values = []
row_index = []
col_index = [0]
for col in range(len(matrix[0])):
for row in range(len(matrix)):
if matrix[row][col]:
values.append(matrix[row][col])
row_index.append(row)
col_index.append(len(values))
return values, row_index, col_index
class Solution:
def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
A = SparseMatrix(mat1, False)
B = SparseMatrix(mat2, True)
ans = [[0] * len(mat2[0]) for _ in range(len(mat1))]
for row in range(len(ans)):
for col in range(len(ans[0])):
# Row element range indices
mat1_row_start = A.row_index[row]
mat1_row_end = A.row_index[row + 1]
# Column element range indices
mat2_col_start = B.col_index[col]
mat2_col_end = B.col_index[col + 1]
# Iterate over both row and column.
while mat1_row_start < mat1_row_end and mat2_col_start < mat2_col_end:
if A.col_index[mat1_row_start] < B.row_index[mat2_col_start]:
mat1_row_start += 1
elif A.col_index[mat1_row_start] > B.row_index[mat2_col_start]:
mat2_col_start += 1
# Row index and col index are same so we can multiply these elements.
else:
ans[row][col] += A.values[mat1_row_start] * B.values[mat2_col_start]
mat1_row_start += 1
mat2_col_start += 1
return ans
C++ code example
class SparseMatrix {
public:
int cols = 0, rows = 0;
vector<int> values, colIndex, rowIndex;
// Compressed Sparse Row
SparseMatrix(vector<vector<int>>& matrix) {
rows = matrix.size();
cols = matrix[0].size();
rowIndex.push_back(0);
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
if (matrix[row][col]) {
values.push_back(matrix[row][col]);
colIndex.push_back(col);
}
}
rowIndex.push_back(values.size());
}
}
// Compressed Sparse Column
SparseMatrix(vector<vector<int>>& matrix, bool colWise) {
rows = matrix.size();
cols = matrix[0].size();
colIndex.push_back(0);
for (int col = 0; col < cols; ++col) {
for (int row = 0; row < rows; ++row) {
if (matrix[row][col]) {
values.push_back(matrix[row][col]);
rowIndex.push_back(row);
}
}
colIndex.push_back(values.size());
}
}
};
class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& mat1, vector<vector<int>>& mat2) {
SparseMatrix A (mat1);
SparseMatrix B (mat2, true);
vector<vector<int>> ans(mat1.size(), vector<int>(mat2[0].size(), 0));
for (int row = 0; row < ans.size(); ++row) {
for (int col = 0; col < ans[0].size(); ++col) {
// Row element range indices
int matrixOneRowStart = A.rowIndex[row];
int matrixOneRowEnd = A.rowIndex[row + 1];
// Column element range indices
int matrixTwoColStart = B.colIndex[col];
int matrixTwoColEnd = B.colIndex[col + 1];
// Iterate over both row and column.
while (matrixOneRowStart < matrixOneRowEnd && matrixTwoColStart < matrixTwoColEnd) {
if (A.colIndex[matrixOneRowStart] < B.rowIndex[matrixTwoColStart]) {
matrixOneRowStart++;
} else if (A.colIndex[matrixOneRowStart] > B.rowIndex[matrixTwoColStart]) {
matrixTwoColStart++;
} else {
// Row index and col index are same so we can multiply these elements.
ans[row][col] += A.values[matrixOneRowStart] * B.values[matrixTwoColStart];
matrixOneRowStart++;
matrixTwoColStart++;
}
}
}
}
return ans;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.