129. Sparse Matrix Multiplication

Why this mechanism works

A[i,p] contributes only through nonzero entries of B's row p. Pre-index those entries, then skip zero A values entirely. This retains the ordinary matrix-product formula while avoiding multiplications known to contribute zero.

State and boundaries

nonzero[p] lists (column,value) entries in B row p. output[i][j] accumulates contributions from processed shared-dimension indices.

Protocol

1. Index nonzero entries of each B row.
2. Allocate the dense output.
3. For each nonzero A[i,p], visit only indexed nonzeros of B[p].
4. Add A[i,p]*B[p,j] to output[i,j].

Visualization

A row [1,0,2]
use B row 0 and twice B row 2
B row 1 contributes nothing for this output row

Python implementation

def sparse_multiply(a, b):
    rows = len(a)
    cols = len(b[0]) if b else 0
    nonzero = [[(j, value) for j, value in enumerate(row) if value != 0]
               for row in b]
    output = [[0] * cols for _ in range(rows)]
    for i, row in enumerate(a):
        for p, value in enumerate(row):
            if value != 0:
                for j, other in nonzero[p]:
                    output[i][j] += value * other
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 sparse_multiply: rows = len(a)
a=[[1, 0, 2]]; b=[[1, 2], [9, 9], [3, 4]]; rows=1

L3 sparse_multiply: cols = len(b[0]) if b else 0
a=[[1, 0, 2]]; b=[[1, 2], [9, 9], [3, 4]]; rows=1; cols=2

L5 sparse_multiply: for row in b]
a=[[1, 0, 2]]; b=[[1, 2], [9, 9], [3, 4]]; rows=1; cols=2; row=[1, 2]

L4 sparse_multiply: nonzero = [[(j, value) for j, value in enumerate(row) if value != 0]
a=[[1, 0, 2]]; b=[[1, 2], [9, 9], [3, 4]]; rows=1; cols=2; row=[1, 2]; j=0; value=1

L4 sparse_multiply: nonzero = [[(j, value) for j, value in enumerate(row) if value != 0]
a=[[1, 0, 2]]; b=[[1, 2], [9, 9], [3, 4]]; rows=1; cols=2; row=[1, 2]; j=1; value=2

L4 sparse_multiply: nonzero = [[(j, value) for j, value in enumerate(row) if value != 0]
a=[[1, 0, 2]]; b=[[1, 2], [9, 9], [3, 4]]; rows=1; cols=2; row=[1, 2]

L5 sparse_multiply: for row in b]
a=[[1, 0, 2]]; b=[[1, 2], [9, 9], [3, 4]]; rows=1; cols=2; row=[9, 9]

L4 sparse_multiply: nonzero = [[(j, value) for j, value in enumerate(row) if value != 0]
a=[[1, 0, 2]]; b=[[1, 2], [9, 9], [3, 4]]; rows=1; cols=2; row=[9, 9]; j=0; value=9

... 17 intermediate state changes omitted ...

L10 sparse_multiply: for j, other in nonzero[p]:
a=[[1, 0, 2]]; b=[[1, 2], [9, 9], [3, 4]]; rows=1; cols=2; nonzero=[[(..., ...), (..., ...)], [(..., ...), (..., ...)], [(..., ...), (..., ...)]]; output=[[1, 2]]; row=[1, 0, 2]; i=0; value=2; p=2; j=0; other=3

L11 sparse_multiply: output[i][j] += value * other
a=[[1, 0, 2]]; b=[[1, 2], [9, 9], [3, 4]]; rows=1; cols=2; nonzero=[[(..., ...), (..., ...)], [(..., ...), (..., ...)], [(..., ...), (..., ...)]]; output=[[7, 2]]; row=[1, 0, 2]; i=0; value=2; p=2; j=0; other=3

L10 sparse_multiply: for j, other in nonzero[p]:
a=[[1, 0, 2]]; b=[[1, 2], [9, 9], [3, 4]]; rows=1; cols=2; nonzero=[[(..., ...), (..., ...)], [(..., ...), (..., ...)], [(..., ...), (..., ...)]]; output=[[7, 2]]; row=[1, 0, 2]; i=0; value=2; p=2; j=1; other=4

L11 sparse_multiply: output[i][j] += value * other
a=[[1, 0, 2]]; b=[[1, 2], [9, 9], [3, 4]]; rows=1; cols=2; nonzero=[[(..., ...), (..., ...)], [(..., ...), (..., ...)], [(..., ...), (..., ...)]]; output=[[7, 10]]; row=[1, 0, 2]; i=0; value=2; p=2; j=1; other=4

L2 sparse_multiply: rows = len(a)
a=[[0, 0]]; b=[[1], [2]]; rows=1

L3 sparse_multiply: cols = len(b[0]) if b else 0
a=[[0, 0]]; b=[[1], [2]]; rows=1; cols=1

L5 sparse_multiply: for row in b]
a=[[0, 0]]; b=[[1], [2]]; rows=1; cols=1; row=[1]

L4 sparse_multiply: nonzero = [[(j, value) for j, value in enumerate(row) if value != 0]
a=[[0, 0]]; b=[[1], [2]]; rows=1; cols=1; row=[1]; j=0; value=1

L4 sparse_multiply: nonzero = [[(j, value) for j, value in enumerate(row) if value != 0]
a=[[0, 0]]; b=[[1], [2]]; rows=1; cols=1; row=[1]

L5 sparse_multiply: for row in b]
a=[[0, 0]]; b=[[1], [2]]; rows=1; cols=1; row=[2]

L4 sparse_multiply: nonzero = [[(j, value) for j, value in enumerate(row) if value != 0]
a=[[0, 0]]; b=[[1], [2]]; rows=1; cols=1; row=[2]; j=0; value=2

L4 sparse_multiply: nonzero = [[(j, value) for j, value in enumerate(row) if value != 0]
a=[[0, 0]]; b=[[1], [2]]; rows=1; cols=1; row=[2]

... 2 intermediate state changes omitted ...

L6 sparse_multiply: output = [[0] * cols for _ in range(rows)]
a=[[0, 0]]; b=[[1], [2]]; rows=1; cols=1; nonzero=[[(..., ...)], [(..., ...)]]; output=[[0]]

L7 sparse_multiply: for i, row in enumerate(a):
a=[[0, 0]]; b=[[1], [2]]; rows=1; cols=1; nonzero=[[(..., ...)], [(..., ...)]]; output=[[0]]; row=[0, 0]; i=0

L8 sparse_multiply: for p, value in enumerate(row):
a=[[0, 0]]; b=[[1], [2]]; rows=1; cols=1; nonzero=[[(..., ...)], [(..., ...)]]; output=[[0]]; row=[0, 0]; i=0; value=0; p=0

L8 sparse_multiply: for p, value in enumerate(row):
a=[[0, 0]]; b=[[1], [2]]; rows=1; cols=1; nonzero=[[(..., ...)], [(..., ...)]]; output=[[0]]; row=[0, 0]; i=0; value=0; p=1

Why the solution is correct

The product definition sums A[i,p]*B[p,j] over every shared index p. Skipped terms have a zero factor and contribute nothing; all nonzero-factor terms are added exactly once to the correct output coordinate. Thus sparsity changes work, not the result.

Time and space

O(kn+mk+mn+W) time, where W is the number of visited nonzero product pairs; O(nnz(B)+mn) space. Worst-case time remains O(mkn) for dense inputs.

Common mistakes

Skipping an entire output column because one A entry is zero loses other contributions. Dense output allocation still costs O(mn), even with sparse inputs.

Reasoning card

Transfer exercise

Represent the output sparsely too, and distinguish multiplication work from the cost of materializing a dense result.