Linear algebra, four ways · 01
Matrix multiplication, four ways
Matrix multiplication
Almost everyone is taught one reading of AB: go along a
row, down a column, sum the products, write the entry. It is correct,
it is the definition, and it explains nothing about what a matrix
product is for. The other three readings do — and two of them
are already running in the posts above this one.
The same product, four procedures. Entry, column,
row, and outer differ in what they compute at each step and in what
is finished when a step ends. They agree on the answer, and the
builder refuses to emit a scene for a reading whose own rule does
not reproduce A @ B.
The four readings
Take A of shape m × k and
B of shape k × n. Every reading below
is the same sum regrouped — which is the whole content of the idea, and
the reason all four have to give the same matrix.
| Reading | One step computes | Steps | Finished per step |
|---|---|---|---|
| entry | AB[i][j] = rowi(A) · colj(B) |
m×n |
one cell, permanently |
| column | colj(AB) = A · colj(B) |
n |
one column, permanently |
| row | rowi(AB) = rowi(A) · B |
m |
one row, permanently |
| outer | colt(A) ⊗ rowt(B) |
k |
nothing — every cell moves |
That last column is the structural difference, and it is worth more
attention than the formulas. Three of the readings partition
the product: each step settles a piece nothing later touches. The outer
reading accumulates: after t of the
k terms, every cell holds a partial sum and none of them
is the answer yet.
Where you have seen the entry reading
A systolic array is the entry reading
built out of wires. The cell at (k, j) holds
B[k][j] and never lets go of it; activation
A[m][k] enters row k and moves one cell right
per cycle; the partial sum for AB[m][j] moves one cell
down and meets each activation exactly when it should. What falls out
of the bottom of column j is rowm(A) ·
colj(B) — an inner product, accumulated in space
rather than in a loop.
The diagonal skew that every explainer draws and nobody justifies is the scheduling consequence of choosing this reading. Pick a different one and you get a different machine.
Where you have seen the outer reading
Tensor parallelism is the outer reading, sharded. The rule everyone repeats is split A by columns and B by rows, usually offered as a convention. It is not a convention. Grouping the rank-1 terms into blocks,
AB = Σt colt(A) ⊗ rowt(B),
so any partition of {1…k} across devices gives each device
a complete set of terms, and the sum of their outputs is the product.
That is the entire argument. A device holding columns
S of A and rows S of
B computes a full-size partial sum by itself, needing
nothing from its peers until the end — which is why an MLP block
crosses the network once. Split A by rows instead
and each device holds fragments of terms rather than whole ones, so
nothing elementwise can be applied yet; the block needs a second
collective, and skipping it computes
Σ relu(partial) where the answer is
relu(Σ partial). Different number, not a rounding
difference.
The tensor-parallel example in this repository asserts both halves: that the column/row pairing reproduces the single-device answer at every split of the FFN dimension, and that the wrong pairing disagrees. The second assertion is the load-bearing one — "the pairing is forced, not conventional" is only worth claiming if skipping the collective is shown to compute something else.
The two nobody builds hardware for
The column reading is the bridge back to a single matrix acting on
space: colj(AB) = A · colj(B) says a
product is just the map A applied once per column of
B, which is why AB composes transformations.
The row reading says each row of the result is a blend of the rows of
B, with a row of A supplying the weights —
the reading that makes a change of basis obvious.
Neither has a counterpart in the dataflow posts above, and that is a fact about what accelerators optimise rather than about the algebra.
Nothing here is drawn
Each reading is executed in ordinary Python, its steps are summed, and
the total is compared against a plain triple-loop
A @ B before any scene source is produced. A reading that
disagrees raises instead of animating:
from straightedge.linalg import VIEWS, check_view, coerce_grid
a, b = coerce_grid([[1, 2], [3, 4]]), coerce_grid([[0, 1], [1, 1]])
for view in VIEWS:
check_view(a, b, view) # raises unless it reproduces A @ B
Every number in the animation is a constant computed that way — the
cell values, the running totals, the captions, the highlighted indices.
Change A or B and all of them follow, because
none of them is typed anywhere. The arithmetic is stdlib on purpose:
the library declares no dependencies, and a closed-form answer is
identical on every machine in a way a LAPACK routine's sign and
ordering conventions are not.
pip install 'straightedge[render]'
python -c "
from straightedge import plan_from_template, write_scene
from pathlib import Path
plan = plan_from_template('linear_algebra/matmul_views',
{'a': [[1,2],[3,4]], 'b': [[0,1],[1,1]], 'view': 'outer'})
write_scene(plan, Path('.'))"
manim -qm scene.py GeneratedSceneA note on what the picture had to lose
The example is 2×2, and 2×2 is small enough that the outer
reading looks like an odd way to do very little work — two rank-1
matrices to produce four numbers. The argument only pays at scale,
where k is thousands and the terms are what get
distributed. The builder refuses anything past 4×4, because the
grids stop being readable before they stop being correct: the library's
own layout checker reports a clean 4×4 and ten overlapping-text
errors at 5×5. Worth stating rather than hiding — a simplification
you cannot see is indistinguishable from an error.