# Convolution Becomes Multiplication

*Task 1 of 5 · [Filtering in the Frequency Domain](https://gpu.rocks/learn/frequency-filtering-8c225e10.md) · GPU.js Learn*

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:

```js
(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.

## Figures

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

## Goal

**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:

```js
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.

## Starter code

```js
// The convolution theorem, both roads at once.
const gpu = new GPU({ mode });

// GIVEN — road 1: direct convolution, the sliding window from
// Convolution & Filters. Output sample x gathers 5 products.
const directConv = gpu.createKernel(function (sig, filt) {
  let sum = 0;
  for (let j = 0; j < this.constants.taps; j++) {
    const t = this.thread.x - j;
    if (t >= 0) {
      sum += sig[t] * filt[j];
    }
  }
  return sum;
}, { output: [64], constants: { taps: 5 } });

// GIVEN — the forward transform. A real signal in, a complex spectrum
// out: with output [n, 2] the result is indexed spec[p][k], where plane 0
// holds the real part of bin k and plane 1 the imaginary part.
const dft = gpu.createKernel(function (sig) {
  const k = this.thread.x;
  let re = 0;
  let im = 0;
  for (let t = 0; t < this.constants.n; t++) {
    const angle = (-2 * Math.PI * k * t) / this.constants.n;
    re += sig[t] * Math.cos(angle);
    im += sig[t] * Math.sin(angle);
  }
  if (this.thread.y === 0) return re;
  return im;
}, { output: [64, 2], constants: { n: 64 } });

// GIVEN — the inverse. A complex spectrum in as spec[0][k] / spec[1][k], a
// complex signal out in the same two planes. The 1/n lives HERE and nowhere
// else: divide a second time "to be safe" and everything comes back n times
// too small.
const idft = gpu.createKernel(function (spec) {
  const t = this.thread.x;
  let re = 0;
  let im = 0;
  for (let k = 0; k < this.constants.n; k++) {
    const angle = (2 * Math.PI * k * t) / this.constants.n;
    const c = Math.cos(angle);
    const s = Math.sin(angle);
    re += spec[0][k] * c - spec[1][k] * s;
    im += spec[0][k] * s + spec[1][k] * c;
  }
  if (this.thread.y === 0) return re / this.constants.n;
  return im / this.constants.n;
}, { output: [64, 2], constants: { n: 64 } });

// YOUR JOB — road 2, the middle step. Multiply the two spectra bin by bin.
const mulSpectra = gpu.createKernel(function (a, b) {
  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];

  // TODO: the two CROSS terms are missing. A complex product is
  // (ar·br − ai·bi) + (ar·bi + ai·br)·i — four products, not two.
  if (this.thread.y === 0) return ar * br;
  return ai * bi;
}, { output: [64, 2] });

const slow = directConv(signal, filt);
const fast = idft(mulSpectra(dft(signal), dft(filt)));

let worst = 0;
let leftover = 0;
for (let i = 0; i < 64; i++) {
  worst = Math.max(worst, Math.abs(fast[0][i] - slow[i]));
  leftover = Math.max(leftover, Math.abs(fast[1][i]));
}
console.log('largest disagreement:', worst.toFixed(9));
console.log('largest imaginary part:', leftover.toFixed(9));
```

---

Interactive version: https://gpu.rocks/learn/frequency-filtering-8c225e10/1

[Next task](https://gpu.rocks/learn/frequency-filtering-8c225e10/2.md)