Sparse Matrix Processing

MediumPython

Problem

Hive's ML inference pipelines may process large, mostly empty feature matrices. Given two sparse matrices in canonical coordinate-list format, return their element-wise sum without converting either matrix to a dense representation.

Each nonzero entry is represented as [row, column, value]. Entries within each matrix are sorted lexicographically by (row, column), and no coordinate appears more than once in the same matrix. The matrices have identical dimensions, although their dimensions are not provided because only stored entries are needed.

Formal Specification

Implement sparse_matrix_sum(matrix_a, matrix_b).

Input: matrix_a and matrix_b, lists of integer triples [row, column, value].
Output: A list of triples containing every nonzero entry in matrix_a + matrix_b, sorted lexicographically by row and column.
If both matrices contain the same coordinate, add their values and omit the coordinate when the sum is zero.
Do not allocate a dense matrix or use a dictionary containing all coordinates.

Constraints

0 <= len(matrix_a), len(matrix_b) <= 10^6
Each entry has exactly three integers: [row, column, value]
0 <= row, column < 10^9
Each input is sorted lexicographically by (row, column)
No coordinate appears more than once within an input
The output contains no zero-valued entries

Function Signature

def sparse_matrix_sum(matrix_a, matrix_b):

Formal Specification

Implement sparse_matrix_sum(matrix_a, matrix_b).

Input: matrix_a and matrix_b, lists of integer triples [row, column, value].
Output: A list of triples containing every nonzero entry in matrix_a + matrix_b, sorted lexicographically by row and column.
If both matrices contain the same coordinate, add their values and omit the coordinate when the sum is zero.
Do not allocate a dense matrix or use a dictionary containing all coordinates.