Vultr DocsLatest Content

Sparse Matrix Multiplication

Updated on 24 June, 2025
Sparse Matrix Multiplication header image

Problem Statement

When provided with two matrices, mat1 and mat2, the task is to compute the matrix product of these two. The matrices are not regular matrices but are "sparse matrices," implying that most of the entries are zero. The dimensions of the matrices are defined such that mat1 has dimensions m x k and mat2 has dimensions k x n. The operation to be performed is feasible as the condition mat1 columns equal to mat2 rows is satisfied (both are equal to k). The output will be a new matrix of dimensions m x n.

Examples

Example 1

Input:

mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]

Output:

[[7,0,0],[-7,0,3]]

Example 2

Input:

mat1 = [[0]], mat2 = [[0]]

Output:

[[0]]

Constraints

  • m == mat1.length
  • k == mat1[i].length == mat2.length
  • n == mat2[i].length
  • 1 <= m, n, k <= 100
  • -100 <= mat1[i][j], mat2[i][j] <= 100

Approach and Intuition

The multiplication of two matrices mat1 of size m x k and mat2 of size k x n implies that the result will be a new matrix whose i-th row and j-th column element will be the dot product of the i-th row vector of mat1 and the j-th column vector of mat2. Here's a simplified step-by-step approach for multiplying two sparse matrices:

  1. Initialize a result matrix of size m x n with all zero values.
  2. Iterate through each element of mat1. For each non-zero element at position (i, j), proceed to the next step.
  3. For every non-zero element in the j-th column of mat2, calculate the product of the element from mat1 and this element from mat2.
  4. Add this product to the proper position (i, k) in the result matrix, where k refers to the column index in mat2 corresponding to the current non-zero element being processed.

Given these points and the example of sparse matrix multiplication shown above, it's clear that a direct computation without considering the sparseness would not be efficient. By focusing only on non-zero elements, we reduce the number of calculations, exploiting the sparse structure for enhanced computational performance. This method is particularly useful in scenarios where the matrix dimensions are large but each matrix contains only a few non-zero elements.

Solutions

  • C++
  • Java
  • JavaScript
  • Python
cpp 
class SparseMatrix {
public:
    int numCols = 0, numRows = 0;
    vector<int> dataValues, columnIndex, rowIndex;

    // Initialize using Compressed Sparse Row format
    SparseMatrix(vector<vector<int>>& matrix) {
        numRows = matrix.size();
        numCols = matrix[0].size(); 
        rowIndex.push_back(0);
        
        for (int r = 0; r < numRows; ++r) {
            for (int c = 0; c < numCols; ++c) {
                if (matrix[r][c] != 0) {
                    dataValues.push_back(matrix[r][c]);
                    columnIndex.push_back(c);
                }
            }
            rowIndex.push_back(dataValues.size());
        }
    }

    // Initialize using Compressed Sparse Column format
    SparseMatrix(vector<vector<int>>& matrix, bool colBased) {
        numRows = matrix.size();
        numCols = matrix[0].size();
        columnIndex.push_back(0);
        
        for (int c = 0; c < numCols; ++c) {
            for (int r = 0; r < numRows; ++r) {
                if (matrix[r][c] != 0) {
                    dataValues.push_back(matrix[r][c]);
                    rowIndex.push_back(r);
                }
            }
            columnIndex.push_back(dataValues.size());
        }
    }
};

class Solution {
public:
    vector<vector<int>> multiply(vector<vector<int>>& mat1, vector<vector<int>>& mat2) {
        SparseMatrix matrix1 (mat1); 
        SparseMatrix matrix2 (mat2, true);
        
        vector<vector<int>> result(mat1.size(), vector<int>(mat2[0].size(), 0));
        
        for (int r = 0; r < result.size(); ++r) {
            for (int c = 0; c < result[0].size(); ++c) {
                
                // Indices for row elements
                int startRowMatrix1 = matrix1.rowIndex[r];
                int endRowMatrix1 = matrix1.rowIndex[r + 1];
                
                // Indices for column elements
                int startColMatrix2 = matrix2.columnIndex[c];
                int endColMatrix2 = matrix2.columnIndex[c + 1];
                
                // Iterate over matching elements
                while (startRowMatrix1 < endRowMatrix1 && startColMatrix2 < endColMatrix2) {
                    if (matrix1.columnIndex[startRowMatrix1] < matrix2.rowIndex[startColMatrix2]) {
                        startRowMatrix1++;
                    } else if (matrix1.columnIndex[startRowMatrix1] > matrix2.rowIndex[startColMatrix2]) {
                        startColMatrix2++;
                    } else {
                        result[r][c] += matrix1.dataValues[startRowMatrix1] * matrix2.dataValues[startColMatrix2];
                        startRowMatrix1++;
                        startColMatrix2++;
                    }
                }
            }
        }
        
        return result;
    }
};

The provided C++ code effectively handles sparse matrix multiplication utilizing the Compressed Sparse Row (CSR) and Compressed Sparse Column (CSC) formats. These formats optimize the storage and multiplication of matrices that contain a large number of zeros. The code executes this through the following steps:

  1. Implement two constructors for the SparseMatrix class to:

    • Handle initialization using the CSR format if provided with just the matrix data.
    • Handle initialization using the CSC format if provided with matrix data and a boolean flag indicating column-based storage.

  2. Each constructor fills the SparseMatrix object's attributes with respective values:

    • numRows and numCols store the matrix dimensions.
    • dataValues holds the nonzero values of the matrix.
    • columnIndex (for CSR) or rowIndex (for CSC) stores the indices of columns or rows respectively where values are non-zero.
    • rowIndex (for CSR) or columnIndex (for CSC) keeps track of the starting index in dataValues for each row or column, respectively.

  3. The multiply function in the Solution class:

    • Initializes two SparseMatrix instances, one for each of the input matrices.
    • Sets up a result matrix with dimensions based on the input matrices but initialized with zeros.
    • Iterates over the result matrix's elements to compute the product using the CSR format of the first matrix and the CSC format of the second matrix. Matching indices in the row vector of the first matrix and the column vector of the second matrix are used to locate and multiply non-zero elements.

This setup ensures efficient memory usage and computational speed for sparse matrices, especially when most elements are zero, by only computing with non-zero elements and skipping an extensive amount of unnecessary multiplication and addition, typical in a naive matrix multiplication approach. This technique is particularly useful in applications such as graph theory, where adjacency matrices are commonly sparse, or in numerical simulations that involve sparse data structures.

java 
class Solution {
    class SparseRepresentation {
        public int columnCount = 0, rowCount = 0;
        public ArrayList<Integer> elementValues = new ArrayList<>(); 
        public ArrayList<Integer> columnIndices = new ArrayList<>(); 
        public ArrayList<Integer> rowStartIndices = new ArrayList<>();

        public SparseRepresentation(int[][] matrix) {
            rowCount = matrix.length;
            columnCount = matrix[0].length; 
            rowStartIndices.add(0);

            for (int i = 0; i < rowCount; ++i) {
                for (int j = 0; j < columnCount; ++j) {
                    if (matrix[i][j] != 0) {
                        elementValues.add(matrix[i][j]);
                        columnIndices.add(j);
                    }
                }
                rowStartIndices.add(elementValues.size());
            }
        }

        public SparseRepresentation(int[][] matrix, boolean columnMode) {
            rowCount = matrix.length;
            columnCount = matrix[0].length;
            columnIndices.add(0);

            for (int j = 0; j < columnCount; ++j) {
                for (int i = 0; i < rowCount; ++i) {
                    if (matrix[i][j] != 0) {
                        elementValues.add(matrix[i][j]);
                        rowStartIndices.add(i);
                    }
                }
                columnIndices.add(elementValues.size());
            }
        }
    };

    
    public int[][] multiplyMatrices(int[][] mat1, int[][] mat2) {
        SparseRepresentation firstMatrix = new SparseRepresentation(mat1); 
        SparseRepresentation secondMatrix = new SparseRepresentation(mat2, true);
        
        int[][] result = new int[mat1.length][mat2[0].length];
        
        for (int i = 0; i < result.length; ++i) {
            for (int j = 0; j < result[0].length; ++j) {
                
                int startRowFirstMatrix = firstMatrix.rowStartIndices.get(i);
                int endRowFirstMatrix = firstMatrix.rowStartIndices.get(i + 1);
                
                int startColumnSecondMatrix = secondMatrix.columnIndices.get(j);
                int endColumnSecondMatrix = secondMatrix.columnIndices.get(j + 1);
                
                while (startRowFirstMatrix < endRowFirstMatrix && startColumnSecondMatrix < endColumnSecondMatrix) {
                    if (firstMatrix.columnIndices.get(startRowFirstMatrix) < secondMatrix.rowStartIndices.get(startColumnSecondMatrix)) {
                        startRowFirstMatrix++;
                    } else if (firstMatrix.columnIndices.get(startRowFirstMatrix) > secondMatrix.rowStartIndices.get(startColumnSecondMatrix)) {
                        startColumnSecondMatrix++;
                    } else {
                        result[i][j] += firstMatrix.elementValues.get(startRowFirstMatrix) * secondMatrix.elementValues.get(startColumnSecondMatrix);
                        startRowFirstMatrix++;
                        startColumnSecondMatrix++;
                    }
                }
            }
        }
        
        return result;
    }
}

The provided Java program is designed to multiply two sparse matrices using a specialized storage format for efficient processing. This implementation is suitable when working with large matrices where most of the elements are zeros. Below is an overview of the solution:

  • Internal Representation of Sparse Matrices:

    • The SparseRepresentation class is used to represent sparse matrices efficiently.
    • It includes arrays for the non-zero element values, their column indices, and row start indices. This format reduces the amount of memory used compared to storing zeros in conventional matrix representations.

  • Multiplication Mechanism:

    • The multiplyMatrices method performs the multiplication of two matrices.
    • It creates SparseRepresentation instances for each matrix. For the second matrix, a column-based representation is used.
    • The result matrix is initialized based on the dimensions of the input matrices (mat1's row count by mat2's column count).
    • The inner loop calculates the dot product of the corresponding row from the first matrix and column from the second matrix, making sure to only compute using the non-zero elements.

  • Efficiency Considerations:

    • This approach focuses on skipping the zero elements, implying that the multiplication complexity depends on the number of non-zero elements rather than the total matrix size.
    • Using sparse matrix representations significantly lowers the number of arithmetic operations needed.

This implementation is particularly effective when dealing with matrices in computing environments where space and time efficiency is critical, such as in machine learning algorithms with large sparse datasets.

js 
class SparseRepresentation {
    constructor(inputMatrix, isColFormat) {
        [this.data, this.indxRows, this.indxCols] = this.createCompressedMatrix(inputMatrix, isColFormat);
    }
    
    createCompressedMatrix(matrix, isColFormat) {
        return (isColFormat ? this.compressColumnWise(matrix) : this.compressRowWise(matrix));
    }
    
    compressRowWise(matrix) {
        let values = []
        let rowIndex = [0]
        let colIndex = []
        
        for (let i = 0; i < matrix.length; ++i) {
            for (let j = 0; j < matrix[0].length; ++j) {
                if (matrix[i][j] !== 0) {
                    values.push(matrix[i][j]);
                    colIndex.push(j);
                }
            }
            rowIndex.push(values.length);
        }
        
        return [values, rowIndex, colIndex];
    }
    
    compressColumnWise(matrix) {
        let values = []
        let rowIndex = []
        let colIndex = [0]
        
        for (let j = 0; j < matrix[0].length; ++j) {
            for (let i = 0; i < matrix.length; ++i) {
                if (matrix[i][j] !== 0) {
                    values.push(matrix[i][j]);
                    rowIndex.push(i);
                }
            }
            colIndex.push(values.length);
        }
        
        return [values, rowIndex, colIndex];
    }
};

let matrixMultiply = function(m1, m2) {
    let A = new SparseRepresentation(m1, false)
    let B = new SparseRepresentation(m2, true)
    
    let result = Array(m1.length).fill().map(() => Array(m2[0].length).fill(0));
    
    result.forEach((_, r) => {
        result[r].forEach((_, c) => {
            let startRow = A.indxRows[r];
            let endRow = A.indxRows[r + 1];
            let startCol = B.indxCols[c];
            let endCol = B.indxCols[c + 1];
            
            while (startRow < endRow && startCol < endCol) {
                if (A.indxCols[startRow] < B.indxRows[startCol]) {
                    startRow++;
                } else if (A.indxCols[startRow] > B.indxRows[startCol]) {
                    startCol++;
                } else {
                    result[r][c] += A.data[startRow] * B.data[startCol];
                    startRow++;
                    startCol++;
                }
            }
        });
    });
    
    return result;
};

This JavaScript implementation provides a solution for multiplying sparse matrices efficiently by leveraging a compressed storage format. The given code introduces the SparseRepresentation class, which can represent matrices in either compressed row storage (CRS) or compressed column storage (CCS) format. These methods reduce memory usage and computational complexity when dealing with sparse matrices, which have a large number of zero entries.

Key Components of the Implementation:

  • SparseRepresentation Class:

    • Constructor takes a matrix and a boolean indicating whether to use column-wise storage.
    • Methods compressRowWise and compressColumnWise return the compressed format of the matrix by extracting non-zero elements and their indices.

  • matrixMultiply Function:

    • Accepts two matrices, m1 and m2.
    • m1 is compressed using row-wise format (CRS).
    • m2 is compressed using column-wise format (CCS).
    • Multiplies the matrices by iterating through rows of A and columns of B, only where non-zero elements meet, optimizing the multiplication process for sparse data.

The resultant array result is populated with the multiplication output. The approach ensures efficient processing by avoiding unnecessary multiplications involving zero entries, crucial for performance in algorithms handling large, sparse matrices. This technique is beneficial in areas like scientific computing, statistics, and machine learning where matrix operations are frequent, but matrices are often sparse.

python 
class CompressedMatrix:
    def __init__(self, matrix: List[List[int]], isColumn: bool):
        self.data, self.rows, self.cols = self.compress(matrix, isColumn)

    def compress(self, matrix: List[List[int]], isColumn: bool):
        return self.column_compress(matrix) if isColumn else self.row_compress(matrix)

    def row_compress(self, matrix: List[List[int]]):
        data = []
        rows = [0]
        cols = []

        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] != 0:
                    data.append(matrix[i][j])
                    cols.append(j)
            rows.append(len(data))

        return data, rows, cols

    def column_compress(self, matrix: List[List[int]]):
        data = []
        rows = []
        cols = [0]

        for j in range(len(matrix[0])):
            for i in range(len(matrix)):
                if matrix[i][j] != 0:
                    data.append(matrix[i][j])
                    rows.append(i)
            cols.append(len(data))

        return data, rows, cols

class MatrixOperations:
    def matrix_multiply(self, matrix1: List[List[int]], matrix2: List[List[int]]) -> List[List[int]]:
        A = CompressedMatrix(matrix1, False)
        B = CompressedMatrix(matrix2, True)

        result = [[0] * len(matrix2[0]) for _ in range(len(matrix1))]

        for i in range(len(result)):
            for j in range(len(result[0])):
                a_start = A.rows[i]
                a_end = A.rows[i + 1]
                b_start = B.cols[j]
                b_end = B.cols[j + 1]

                while a_start < a_end and b_start < b_end:
                    if A.cols[a_start] < B.rows[b_start]:
                        a_start += 1
                    elif A.cols[a_start] > B.rows[b_start]:
                        b_start += 1
                    else:
                        result[i][j] += A.data[a_start] * B.data[b_start]
                        a_start += 1
                        b_start += 1

        return result

In the provided Python solution for "Sparse Matrix Multiplication," you work with a class-based approach that focuses on optimized matrix storage and multiplication for sparse matrices. The solution comprises two main classes: CompressedMatrix and MatrixOperations.

  • A CompressedMatrix class is utilized for compressing the sparse matrix in either row-major or column-major format depending on the boolean parameter isColumn. This class methodically compresses non-zero elements into three lists: data, rows (or cols, depending on the compression style), and cols (or rows, respectively). This compression helps to efficiently manage space and improve manipulation speeds of sparse matrices.

  • The MatrixOperations class contains a matrix_multiply method responsible for performing the actual multiplication of two matrices. This method first compresses the input matrices. It compresses the first matrix using the row-major method and the second matrix using the column-major method to align both for multiplication. For each potential non-zero result element, the method goes through the non-zero elements of the relevant rows and columns, checking for alignment by index positions and performing multiplications and additions as required.

This method effectively leverages the sparsity of matrices to avoid unnecessary multiplications with zero, thus optimizing the complexity and run-time of matrix multiplication operations, especially beneficial for very large matrices with high sparsity levels. Through careful alignment checks and selective multiplication, the implementation ensures data efficiency and computational speed.

Comments

No comments yet.