AlgoVerse

Sparse matrix multiplication

Keep each row by its non-zero terms only and do only the non-zero products; far fewer than n³ for sparse matrices.

In a sparse matrix most products A[i][k]·B[k][j] are zero and doing them is wasted work. If each row is kept by its non-zero terms only:

Read the full explanation ↓
Input:
A 4×4 · B 4×4PDF export

Two 4×4 matrices with mostly zero cells; only 5 products are needed instead of 64.

  1. def sparse_multiply(A, B):
  2. if len(A[0]) != len(B):
  3. return None
  4. # Row lists: for each row, only its non-zero (column, value) pairs.
  5. a_rows = [[(j, v) for j, v in enumerate(row) if v != 0] for row in A]
  6. b_rows = [[(j, v) for j, v in enumerate(row) if v != 0] for row in B]
  7. C = []
  8. products = 0
  9. for i in range(len(A)):
  10. acc = {}
  11. for k, a in a_rows[i]:
  12. for j, b in b_rows[k]:
  13. acc[j] = acc.get(j, 0) + a * b
  14. products = products + 1
  15. C.append(sorted((j, v) for j, v in acc.items() if v != 0))
  16. return products

Invariant: Every product done multiplies two non-zero terms, and A[i][k]·B[k][j] is only added to cell (i, j) of the result.

Start

products—

a_rows

The table is still empty.

b_rows

The table is still empty.

C

The table is still empty.

Local variables

Orange = changed in this step

A list

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

B list

[0, 5, 0, 0][0, 0, 0, 0][6, 0, 0, 7][0, 0, 8, 0]

Call stack

  1. sparse_multiply()line 1
Step 1 of 47
Black = row_done · Orange = key steprow_lists: 0/1 · product: 0/5 · row_done: 0/4
    Explanation

    The idea

    In a sparse matrix most products A[i][k]·B[k][j] are zero and doing them is wasted work. If each row is kept by its non-zero terms only:

    • for row i of A, multiply each non-zero A[i][k] by the non-zero terms of row k of B, adding into acc[j];
    • acc is row i of the result; zeros are dropped.

    Cost

    The number of products is exactly the number of non-zero pairs (A[i][k], B[k][j]), far fewer than n³ for sparse matrices. Horowitz–Sahni do the same with triples and the transpose of B; the idea is the same.

    What to watch in the trace

    • The a_rows and b_rows tables list each row's non-zero terms, and C is the result in the same form. products counts the products done.