The operation now deserves a name
You have already built the operation: take every cross-list pair, multiply it, route it by the sum of the two input positions, and add products that share a destination.
The star ∗ names convolution. The formula is the backward bucket view from the previous section. Terms with an out-of-range index are omitted or treated as zero.
Derive the algorithm from the definition
The definition offers two equivalent implementation strategies. A scatter algorithm visits each input pair (i,k) and adds its product to output i+k. A gather algorithm visits each output t and searches for valid i whose partner is t−i. They organize the loops differently but enumerate the same records.
# scatter
for i in range(L):
for k in range(M):
c[i + k] += a[i] * b[k]# gather
for t in range(L + M - 1):
for i in valid_left_indices(t):
c[t] += a[i] * b[t - i]Construct it in live Python
The notebook below begins with editable coefficients, enumerates every pair, exposes the accumulation trace, then changes only the boundary rule. Its cells are intentionally small so the program grows in the same order as the mathematics.
Construct every pair, route it to a bucket, and change only the boundary rule to obtain negacyclic multiplication.
Runs entirely in this browser. Python executes in Pyodide WebAssembly with no remote kernel. The construction code stays visible while reactive dependents recompute whenever you change an input.
Worked example
Convolve [1,2,1] with [3,−1]
Verify structural properties with the pair records
Swapping (i,k) to (k,i) preserves both the product and destination sum.
The only right index is zero, so every value keeps its position and magnitude.
Ordinary multiplication distributes inside every bucket.
These are not merely algebra trivia. Each property provides a test oracle. A correct implementation should agree when inputs are swapped and should return the original input when convolved with [1].
Check your understanding
What should [2,−3,5] ∗ [1] return?
Three operations that learners often merge
Check your understanding
Which statement distinguishes convolution from a dot product?
Why convolution appears in many fields
The bucket rule describes overlapping effects. In audio, a short impulse response contributes shifted copies to an output signal. In image processing, a filter combines nearby pixels. In probability, sums of independent discrete outcomes collect products of probabilities whose outcome values add. These applications differ, but the index arithmetic is the same.
Optional: connect polynomial multiplication and convolution
If A(x) and B(x) use a and b as coefficient lists, the coefficient list of A(x)B(x) is exactly a∗b. “Polynomial multiplication” and “coefficient convolution” describe two views of the same operation.
Measure the straightforward work
The scatter implementation performs L·M coefficient multiplications and the same number of bucket updates, so its running time is O(LM). When both inputs have length N, this is O(N²). Later algorithms may reorganize this work, but the direct version remains our correctness reference because its pair-to-bucket behavior is completely visible.
Check your understanding
For lengths 3 and 2, how many output buckets does linear convolution have?
Section summary
- Convolution is the output-bucket rule you already built.
- It uses every input pair.
- Polynomial products and coefficient convolutions are the same calculation.
- It differs fundamentally from same-index operations.
Repository layer · second pass
How does convolution name the bucket process we already understand?
Linear convolution is the complete list of bucket totals. Its t-th output is the sum of every aᵢbₜ₋ᵢ whose indices exist. The compact formula does not introduce a new operation; it quantifies the diagonal walk built in the previous section.
Convolution differs from a dot product in its pairing rule and output shape. A dot product fixes equality i=i and reduces to one scalar. Convolution fixes a sum i+k=t and produces many bucket totals. The inner-product trick will later alter storage so equality implies one chosen constant sum.
Reasoning chain
- 1
Allocate L+R−1 zero buckets.
- 2
Visit each input pair once.
- 3
Compute destination i+k.
- 4
Accumulate, never overwrite, at that destination.
- 5
Verify against the diagonal formula independently.
Worked trace
Trace all nine pairs
- Use A=[2,−1,3] and B=[4,5,−2].
- Edge buckets receive 8 and −6.
- Interior totals are 10−4=6, −4−5+12=3, and 2+15=17.
- Keep the destination trace beside the result.
Result. A*B = [8,6,3,17,−6].
Executable lens · Python
Make the hidden state visible
def convolve(a, b):
out = [0] * (len(a) + len(b) - 1)
for i, left in enumerate(a):
for k, right in enumerate(b):
out[i + k] += left * right
return out
assert convolve([2,-1,3], [4,5,-2]) == [8,6,3,17,-6]Retype this example, predict each intermediate value, and then change one input that touches a boundary.
Misconception clinic
Tempting mistakes
- Overwriting a bucket instead of accumulating.
- Assuming convolution automatically means circular wrap.
Retrieval and transfer
Close the book first
- Implement convolution with a bucket-first loop instead of a pair-first loop.
- Find an input where an interior bucket cancels to zero.
- State the exact invariant preserved by both loop nest orders.