Task 1 of 5

Convolution Becomes Multiplication

Convolution & Filters slid a window along a signal: every output sample gathered m products, so the whole pass cost n·m. This task makes that sliding window disappear.

The convolution theorem says: transform both signals, multiply the two spectra bin by bin, transform back — and what comes out is the convolution. No window, no m. The cost collapses to the cost of the transforms, which is why every audio plug-in, every software radio and every large-kernel blur is written this way. We are going to check that claim rather than believe it.

Every task in this module hands you a finished dft/idft pair and asks you to write only the step between them. They are the naive O(n²) transforms rather than the ladder The FFT Butterfly builds, because which transform produced a spectrum changes none of the arithmetic below — and the arithmetic below is the whole point.

Spectra are complex, and gpu.js has no complex type, so this track carries a complex signal as two planes of floats. A kernel with output: [n, 2] is indexed result[p][i] — plane 0 the real part, plane 1 the imaginary part, i the bin. Handed back into a kernel the same thing is a [2][n] nested array: spec[0][i] real, spec[1][i] imaginary. Every module in this track uses that shape.

Multiplying two complex numbers is where people slip. It is not "reals times reals, imaginaries times imaginaries" — that is four products, and two of them cross:

(ar + ai·i)(br + bi·i) = (ar·br − ai·bi) + (ar·bi + ai·br)·i

Drop the cross terms and you get a specific, recognisable wrong answer — which is exactly what the starter below does, so run it first and watch the two roads disagree.

the long way round is the fast way — and it arrives at the same numbers

Goal: finish mulSpectra so the frequency-domain road reproduces the sliding window's answer — the two should agree to five or six decimal places, and whatever is left is float32 rounding rather than physics.

Requirements

Keep output: [64, 2] — plane 0 is the real part of each bin, plane 1 the imaginary part
Read both planes of both arguments: a[0][i], a[1][i], b[0][i], b[1][i]
Plane 0 returns ar * br - ai * bi; plane 1 returns ar * bi + ai * br — all four products, both cross terms
Leave the 1/n to idft: the inverse transform already has it

Hint 1 — which plane am I?

With output: [64, 2] there are 128 threads. this.thread.x is the bin, 0…63; this.thread.y is the plane, 0 for real and 1 for imaginary. Every thread reads all four numbers — the four products mix both planes of both inputs — and returns just the one belonging to its own plane.

Hint 2 — the four products

Name them first, then pick:

const i = this.thread.x;
const ar = a[0][i];
const ai = a[1][i];
const br = b[0][i];
const bi = b[1][i];

if (this.thread.y === 0) return ar * br - ai * bi;
return ar * bi + ai * br;

Both signs matter. Flip the one in the real part and you have computed a times the conjugate of b, which correlates instead of convolving — the filter comes out reversed in time.

Same idea elsewhere

This is the one trade every FFT library exists to sell. In CUDA it is three calls: cufftExecC2C forward, a handful of lines of cuComplex multiply, cufftExecC2C inverse — and cuComplex is there so the four products get written once instead of in every kernel. ROCm ships rocFFT, Apple ships vDSP and MPS, and WebGPU ships nothing at all, so everyone writes the same radix-2 ladder over a storage buffer. The two planes you are indexing here are what a float2 buffer or an rg32float texture holds on every one of them.

All tasks in Filtering in the Frequency Domain

This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.