Complexity of the Multidimensional FFT

Introduction

Every digital image is a grid of numbers. When you blur a photo, sharpen an edge, or compress a JPEG, something remarkable happens under the hood: the image is decomposed into frequencies. Low frequencies carry the broad shapes; high frequencies carry sharp edges and fine texture. That decomposition is the Discrete Fourier Transform (DFT).

For a one-dimensional signal of length $N$ , the DFT of a sequence $x$ is

X[k] = \sum_{n=0}^{N-1} x[n]\, e^{-2\pi i \frac{kn}{N}}, \quad k = 0, 1, \dots, N-1.

Computing all $N$ outputs naively takes $O(N^2)$ multiplications. The Fast Fourier Transform (FFT), introduced by Cooley and Tukey in 1965, reduces this to $O(N \log N)$ by recursively splitting even and odd indices — one of the most celebrated algorithms of the 20th century.

But images are two-dimensional, and medical scans or climate models are three-dimensional or more. How does the FFT extend? The key insight is separability: the multidimensional DFT can be computed by applying the 1D FFT repeatedly along each axis in turn. No new mathematics is needed — just the same elegant divide-and-conquer, swept across every dimension.

See the Frequency Spectrum

Draw on the left grid — click or drag to toggle pixels on and off. The right panel shows the 2D FFT magnitude spectrum (log scale, center-shifted so DC sits in the middle). The transform is recomputed live, axis by axis, every time you change a pixel.

<!-- Wrapper: left panel = input pixel grid; right panel = FFT magnitude spectrum -->
<div class="demo-wrap">
  <div class="panel">
    <div class="panel-label">Input pixels</div>
    <canvas id="inputCanvas" width="128" height="128" title="Click or drag to draw pixels"></canvas>
    <div class="controls">
      <button id="btnClear" type="button">Clear</button>
      <button id="btnHStripe" type="button">H-stripe</button>
      <button id="btnVStripe" type="button">V-stripe</button>
      <button id="btnChecker" type="button">Checkerboard</button>
    </div>
  </div>
  <div class="panel">
    <div class="panel-label">Frequency spectrum (log, centered)</div>
    <canvas id="specCanvas" width="128" height="128" aria-label="2D FFT magnitude spectrum — bright pixels indicate strong frequency components"></canvas>
    <div class="info" id="info">Draw pixels, then watch the spectrum update.</div>
  </div>
</div>

/* Base layout: two side-by-side panels */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; background: #f5f7fa; }
.demo-wrap {
  display: flex; gap: 16px; flex-wrap: wrap;
  justify-content: center; padding: 12px;
}
.panel {
  display: flex; flex-direction: column; align-items: center; gap: 8px;
}
.panel-label {
  font-size: .82rem; font-weight: 600; color: #5a7088; letter-spacing: .03em;
  text-transform: uppercase;
}
canvas {
  border: 1.5px solid #cdd9e3; border-radius: 6px;
  cursor: crosshair; image-rendering: pixelated;
  width: 160px; height: 160px;
}
/* Spectrum canvas has no crosshair cursor */
#specCanvas { cursor: default; }
.controls {
  display: flex; gap: 6px; flex-wrap: wrap; justify-content: center;
}
button {
  font: 600 12px system-ui; padding: .35rem .7rem;
  border: 1px solid #1d3557; background: #1d3557;
  color: #fff; border-radius: 6px; cursor: pointer;
}
button:hover { background: #16294a; }
.info {
  font-size: .8rem; color: #5a7088; text-align: center;
  min-height: 1.2em; max-width: 200px; line-height: 1.4;
}

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* 2D FFT via row-column (separability): apply 1D FFT to every row, then every column */
const N = 16; /* Grid is NxN (must be a power of two for Cooley-Tukey) */

/* In-place Cooley-Tukey radix-2 FFT: bit-reversal permutation then butterfly passes */
function fft1d(re, im) {
  const n = re.length;
  if (n <= 1) return;
  /* Bit-reversal permutation — reorder elements so butterflies are in-place */
  let j = 0;
  for (let i = 1; i < n; i++) {
    let bit = n >> 1;
    for (; j & bit; bit >>= 1) j ^= bit;
    j ^= bit;
    if (i < j) {
      [re[i], re[j]] = [re[j], re[i]];
      [im[i], im[j]] = [im[j], im[i]];
    }
  }
  /* Butterfly passes — combine pairs with twiddle factors */
  for (let len = 2; len <= n; len <<= 1) {
    const ang = -2 * Math.PI / len;
    const wRe = Math.cos(ang), wIm = Math.sin(ang);
    for (let i = 0; i < n; i += len) {
      let curRe = 1, curIm = 0;
      for (let k = 0; k < len / 2; k++) {
        const uRe = re[i + k], uIm = im[i + k];
        const vRe = re[i + k + len / 2] * curRe - im[i + k + len / 2] * curIm;
        const vIm = re[i + k + len / 2] * curIm + im[i + k + len / 2] * curRe;
        re[i + k] = uRe + vRe; im[i + k] = uIm + vIm;
        re[i + k + len / 2] = uRe - vRe; im[i + k + len / 2] = uIm - vIm;
        const nxtRe = curRe * wRe - curIm * wIm;
        curIm = curRe * wIm + curIm * wRe; curRe = nxtRe;
      }
    }
  }
}

/* Separable 2D FFT: row pass then column pass */
function fft2d(grid) {
  const re = [], im = [];
  /* Copy input grid into complex arrays (imaginary part = 0) */
  for (let r = 0; r < N; r++) {
    re.push([...grid[r]]);
    im.push(new Array(N).fill(0));
  }
  /* Pass 1: apply 1D FFT to each row */
  for (let r = 0; r < N; r++) fft1d(re[r], im[r]);
  /* Pass 2: apply 1D FFT to each column of intermediate result */
  for (let c = 0; c < N; c++) {
    const colRe = re.map(row => row[c]);
    const colIm = im.map(row => row[c]);
    fft1d(colRe, colIm);
    for (let r = 0; r < N; r++) { re[r][c] = colRe[r]; im[r][c] = colIm[r]; }
  }
  return { re, im };
}

/* Compute magnitude (absolute value) of each complex frequency bin */
function magnitude(re, im) {
  return re.map((row, r) => row.map((v, c) => Math.sqrt(v * v + im[r][c] * im[r][c])));
}

/* Shift DC to center: wrap by N/2 in both dimensions */
function fftshift(mag) {
  const h = N / 2;
  return mag.map((row, r) => row.map((_, c) => mag[(r + h) % N][(c + h) % N]));
}

/* Normalize to [0,1] using log scale so weak frequencies are still visible */
function logScale(mag) {
  const flat = mag.flat();
  const maxVal = Math.max(...flat);
  return mag.map(row => row.map(v => Math.log1p(v) / Math.log1p(maxVal)));
}

/* State: NxN pixel grid (0=off, 1=on); drawing flag */
const pixels = Array.from({ length: N }, () => new Array(N).fill(0));
let isDrawing = false;

const inputCanvas = document.getElementById('inputCanvas');
const specCanvas = document.getElementById('specCanvas');
const inCtx = inputCanvas.getContext('2d');
const spCtx = specCanvas.getContext('2d');
const infoEl = document.getElementById('info');

/* Render the input pixel grid on the left canvas */
function drawInput() {
  const cw = inputCanvas.width, ch = inputCanvas.height;
  const px = cw / N, py = ch / N;
  inCtx.clearRect(0, 0, cw, ch);
  for (let r = 0; r < N; r++) {
    for (let c = 0; c < N; c++) {
      inCtx.fillStyle = pixels[r][c] ? '#1d3557' : '#eef1f5';
      inCtx.fillRect(c * px, r * py, px - 1, py - 1);
    }
  }
}

/* Compute and render the FFT magnitude spectrum on the right canvas */
function drawSpectrum() {
  const { re, im } = fft2d(pixels);
  const mag = magnitude(re, im);
  const shifted = fftshift(mag);
  const normed = logScale(shifted);
  const cw = specCanvas.width, ch = specCanvas.height;
  const px = cw / N, py = ch / N;
  spCtx.clearRect(0, 0, cw, ch);
  for (let r = 0; r < N; r++) {
    for (let c = 0; c < N; c++) {
      const v = Math.round(normed[r][c] * 255);
      spCtx.fillStyle = `rgb(${v},${v},${v})`;
      spCtx.fillRect(c * px, r * py, px - 1, py - 1);
    }
  }
}

function update() { drawInput(); drawSpectrum(); }

/* Convert mouse/touch event to (row, col) grid coordinates */
function pixelFrom(e) {
  const rect = inputCanvas.getBoundingClientRect();
  const x = (e.clientX - rect.left) / rect.width;
  const y = (e.clientY - rect.top) / rect.height;
  return { r: Math.floor(y * N), c: Math.floor(x * N) };
}

function togglePixel(e) {
  const { r, c } = pixelFrom(e);
  if (r < 0 || r >= N || c < 0 || c >= N) return;
  pixels[r][c] = pixels[r][c] ? 0 : 1;
  infoEl.textContent = i18nFmt('%n% pixel(s) active.', { n: pixels.flat().filter(Boolean).length });
  update();
}

function paintPixel(e) {
  if (!isDrawing) return;
  const { r, c } = pixelFrom(e);
  if (r < 0 || r >= N || c < 0 || c >= N) return;
  if (!pixels[r][c]) { pixels[r][c] = 1; infoEl.textContent = i18nFmt('%n% pixel(s) active.', { n: pixels.flat().filter(Boolean).length }); update(); }
}

inputCanvas.addEventListener('mousedown', e => { isDrawing = true; togglePixel(e); });
inputCanvas.addEventListener('mousemove', paintPixel);
inputCanvas.addEventListener('mouseup', () => { isDrawing = false; });
inputCanvas.addEventListener('mouseleave', () => { isDrawing = false; });

/* Touch events for mobile drawing — prevent scroll while drawing */
inputCanvas.addEventListener('touchstart', e => {
  e.preventDefault(); isDrawing = true; togglePixel(e.touches[0]);
}, { passive: false });
inputCanvas.addEventListener('touchmove', e => {
  e.preventDefault(); paintPixel(e.touches[0]);
}, { passive: false });
inputCanvas.addEventListener('touchend', () => { isDrawing = false; });

/* Preset buttons — each loads a pattern that has a distinctive spectrum */
document.getElementById('btnClear').addEventListener('click', () => {
  for (let r = 0; r < N; r++) pixels[r].fill(0);
  infoEl.textContent = 'Draw pixels, then watch the spectrum update.';
  update();
});
document.getElementById('btnHStripe').addEventListener('click', () => {
  for (let r = 0; r < N; r++) for (let c = 0; c < N; c++) pixels[r][c] = (r === N / 2) ? 1 : 0;
  infoEl.textContent = 'Horizontal stripe → energy on vertical axis of spectrum.';
  update();
});
document.getElementById('btnVStripe').addEventListener('click', () => {
  for (let r = 0; r < N; r++) for (let c = 0; c < N; c++) pixels[r][c] = (c === N / 2) ? 1 : 0;
  infoEl.textContent = 'Vertical stripe → energy on horizontal axis of spectrum.';
  update();
});
document.getElementById('btnChecker').addEventListener('click', () => {
  for (let r = 0; r < N; r++) for (let c = 0; c < N; c++) pixels[r][c] = (r + c) % 2;
  infoEl.textContent = 'Checkerboard → energy at the four corners (max frequency).';
  update();
});

/* Initial pattern — symmetric dots so the demo starts with an interesting spectrum */
pixels[4][4] = 1; pixels[4][11] = 1; pixels[11][4] = 1; pixels[11][11] = 1;
pixels[7][7] = 1; pixels[7][8] = 1; pixels[8][7] = 1; pixels[8][8] = 1;
update();

<!-- Wrapper: left panel = input pixel grid; right panel = FFT magnitude spectrum -->
<div class="demo-wrap">
  <div class="panel">
    <div class="panel-label">Input pixels</div>
    <canvas id="inputCanvas" width="128" height="128" title="Click or drag to draw pixels"></canvas>
    <div class="controls">
      <button id="btnClear" type="button">Clear</button>
      <button id="btnHStripe" type="button">H-stripe</button>
      <button id="btnVStripe" type="button">V-stripe</button>
      <button id="btnChecker" type="button">Checkerboard</button>
    </div>
  </div>
  <div class="panel">
    <div class="panel-label">Frequency spectrum (log, centered)</div>
    <canvas id="specCanvas" width="128" height="128" aria-label="2D FFT magnitude spectrum — bright pixels indicate strong frequency components"></canvas>
    <div class="info" id="info">Draw pixels, then watch the spectrum update.</div>
  </div>
</div>

/* Base layout: two side-by-side panels */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; background: #f5f7fa; }
.demo-wrap {
  display: flex; gap: 16px; flex-wrap: wrap;
  justify-content: center; padding: 12px;
}
.panel {
  display: flex; flex-direction: column; align-items: center; gap: 8px;
}
.panel-label {
  font-size: .82rem; font-weight: 600; color: #5a7088; letter-spacing: .03em;
  text-transform: uppercase;
}
canvas {
  border: 1.5px solid #cdd9e3; border-radius: 6px;
  cursor: crosshair; image-rendering: pixelated;
  width: 160px; height: 160px;
}
/* Spectrum canvas has no crosshair cursor */
#specCanvas { cursor: default; }
.controls {
  display: flex; gap: 6px; flex-wrap: wrap; justify-content: center;
}
button {
  font: 600 12px system-ui; padding: .35rem .7rem;
  border: 1px solid #1d3557; background: #1d3557;
  color: #fff; border-radius: 6px; cursor: pointer;
}
button:hover { background: #16294a; }
.info {
  font-size: .8rem; color: #5a7088; text-align: center;
  min-height: 1.2em; max-width: 200px; line-height: 1.4;
}

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* 2D FFT via row-column (separability): apply 1D FFT to every row, then every column */
const N = 16; /* Grid is NxN (must be a power of two for Cooley-Tukey) */

/* In-place Cooley-Tukey radix-2 FFT: bit-reversal permutation then butterfly passes */
function fft1d(re, im) {
  const n = re.length;
  if (n <= 1) return;
  /* Bit-reversal permutation — reorder elements so butterflies are in-place */
  let j = 0;
  for (let i = 1; i < n; i++) {
    let bit = n >> 1;
    for (; j & bit; bit >>= 1) j ^= bit;
    j ^= bit;
    if (i < j) {
      [re[i], re[j]] = [re[j], re[i]];
      [im[i], im[j]] = [im[j], im[i]];
    }
  }
  /* Butterfly passes — combine pairs with twiddle factors */
  for (let len = 2; len <= n; len <<= 1) {
    const ang = -2 * Math.PI / len;
    const wRe = Math.cos(ang), wIm = Math.sin(ang);
    for (let i = 0; i < n; i += len) {
      let curRe = 1, curIm = 0;
      for (let k = 0; k < len / 2; k++) {
        const uRe = re[i + k], uIm = im[i + k];
        const vRe = re[i + k + len / 2] * curRe - im[i + k + len / 2] * curIm;
        const vIm = re[i + k + len / 2] * curIm + im[i + k + len / 2] * curRe;
        re[i + k] = uRe + vRe; im[i + k] = uIm + vIm;
        re[i + k + len / 2] = uRe - vRe; im[i + k + len / 2] = uIm - vIm;
        const nxtRe = curRe * wRe - curIm * wIm;
        curIm = curRe * wIm + curIm * wRe; curRe = nxtRe;
      }
    }
  }
}

/* Separable 2D FFT: row pass then column pass */
function fft2d(grid) {
  const re = [], im = [];
  /* Copy input grid into complex arrays (imaginary part = 0) */
  for (let r = 0; r < N; r++) {
    re.push([...grid[r]]);
    im.push(new Array(N).fill(0));
  }
  /* Pass 1: apply 1D FFT to each row */
  for (let r = 0; r < N; r++) fft1d(re[r], im[r]);
  /* Pass 2: apply 1D FFT to each column of intermediate result */
  for (let c = 0; c < N; c++) {
    const colRe = re.map(row => row[c]);
    const colIm = im.map(row => row[c]);
    fft1d(colRe, colIm);
    for (let r = 0; r < N; r++) { re[r][c] = colRe[r]; im[r][c] = colIm[r]; }
  }
  return { re, im };
}

/* Compute magnitude (absolute value) of each complex frequency bin */
function magnitude(re, im) {
  return re.map((row, r) => row.map((v, c) => Math.sqrt(v * v + im[r][c] * im[r][c])));
}

/* Shift DC to center: wrap by N/2 in both dimensions */
function fftshift(mag) {
  const h = N / 2;
  return mag.map((row, r) => row.map((_, c) => mag[(r + h) % N][(c + h) % N]));
}

/* Normalize to [0,1] using log scale so weak frequencies are still visible */
function logScale(mag) {
  const flat = mag.flat();
  const maxVal = Math.max(...flat);
  return mag.map(row => row.map(v => Math.log1p(v) / Math.log1p(maxVal)));
}

/* State: NxN pixel grid (0=off, 1=on); drawing flag */
const pixels = Array.from({ length: N }, () => new Array(N).fill(0));
let isDrawing = false;

const inputCanvas = document.getElementById('inputCanvas');
const specCanvas = document.getElementById('specCanvas');
const inCtx = inputCanvas.getContext('2d');
const spCtx = specCanvas.getContext('2d');
const infoEl = document.getElementById('info');

/* Render the input pixel grid on the left canvas */
function drawInput() {
  const cw = inputCanvas.width, ch = inputCanvas.height;
  const px = cw / N, py = ch / N;
  inCtx.clearRect(0, 0, cw, ch);
  for (let r = 0; r < N; r++) {
    for (let c = 0; c < N; c++) {
      inCtx.fillStyle = pixels[r][c] ? '#1d3557' : '#eef1f5';
      inCtx.fillRect(c * px, r * py, px - 1, py - 1);
    }
  }
}

/* Compute and render the FFT magnitude spectrum on the right canvas */
function drawSpectrum() {
  const { re, im } = fft2d(pixels);
  const mag = magnitude(re, im);
  const shifted = fftshift(mag);
  const normed = logScale(shifted);
  const cw = specCanvas.width, ch = specCanvas.height;
  const px = cw / N, py = ch / N;
  spCtx.clearRect(0, 0, cw, ch);
  for (let r = 0; r < N; r++) {
    for (let c = 0; c < N; c++) {
      const v = Math.round(normed[r][c] * 255);
      spCtx.fillStyle = `rgb(${v},${v},${v})`;
      spCtx.fillRect(c * px, r * py, px - 1, py - 1);
    }
  }
}

function update() { drawInput(); drawSpectrum(); }

/* Convert mouse/touch event to (row, col) grid coordinates */
function pixelFrom(e) {
  const rect = inputCanvas.getBoundingClientRect();
  const x = (e.clientX - rect.left) / rect.width;
  const y = (e.clientY - rect.top) / rect.height;
  return { r: Math.floor(y * N), c: Math.floor(x * N) };
}

function togglePixel(e) {
  const { r, c } = pixelFrom(e);
  if (r < 0 || r >= N || c < 0 || c >= N) return;
  pixels[r][c] = pixels[r][c] ? 0 : 1;
  infoEl.textContent = i18nFmt('%n% pixel(s) active.', { n: pixels.flat().filter(Boolean).length });
  update();
}

function paintPixel(e) {
  if (!isDrawing) return;
  const { r, c } = pixelFrom(e);
  if (r < 0 || r >= N || c < 0 || c >= N) return;
  if (!pixels[r][c]) { pixels[r][c] = 1; infoEl.textContent = i18nFmt('%n% pixel(s) active.', { n: pixels.flat().filter(Boolean).length }); update(); }
}

inputCanvas.addEventListener('mousedown', e => { isDrawing = true; togglePixel(e); });
inputCanvas.addEventListener('mousemove', paintPixel);
inputCanvas.addEventListener('mouseup', () => { isDrawing = false; });
inputCanvas.addEventListener('mouseleave', () => { isDrawing = false; });

/* Touch events for mobile drawing — prevent scroll while drawing */
inputCanvas.addEventListener('touchstart', e => {
  e.preventDefault(); isDrawing = true; togglePixel(e.touches[0]);
}, { passive: false });
inputCanvas.addEventListener('touchmove', e => {
  e.preventDefault(); paintPixel(e.touches[0]);
}, { passive: false });
inputCanvas.addEventListener('touchend', () => { isDrawing = false; });

/* Preset buttons — each loads a pattern that has a distinctive spectrum */
document.getElementById('btnClear').addEventListener('click', () => {
  for (let r = 0; r < N; r++) pixels[r].fill(0);
  infoEl.textContent = 'Draw pixels, then watch the spectrum update.';
  update();
});
document.getElementById('btnHStripe').addEventListener('click', () => {
  for (let r = 0; r < N; r++) for (let c = 0; c < N; c++) pixels[r][c] = (r === N / 2) ? 1 : 0;
  infoEl.textContent = 'Horizontal stripe → energy on vertical axis of spectrum.';
  update();
});
document.getElementById('btnVStripe').addEventListener('click', () => {
  for (let r = 0; r < N; r++) for (let c = 0; c < N; c++) pixels[r][c] = (c === N / 2) ? 1 : 0;
  infoEl.textContent = 'Vertical stripe → energy on horizontal axis of spectrum.';
  update();
});
document.getElementById('btnChecker').addEventListener('click', () => {
  for (let r = 0; r < N; r++) for (let c = 0; c < N; c++) pixels[r][c] = (r + c) % 2;
  infoEl.textContent = 'Checkerboard → energy at the four corners (max frequency).';
  update();
});

/* Initial pattern — symmetric dots so the demo starts with an interesting spectrum */
pixels[4][4] = 1; pixels[4][11] = 1; pixels[11][4] = 1; pixels[11][11] = 1;
pixels[7][7] = 1; pixels[7][8] = 1; pixels[8][7] = 1; pixels[8][8] = 1;
update();

Result

Console

Try drawing a horizontal stripe: energy concentrates along the vertical axis of the spectrum (vertical frequencies). Draw a vertical stripe and energy shifts to the horizontal axis. A checkerboard pattern pushes energy to the four corners — the highest frequencies in both directions. This is separability made visible: the 2D spectrum is the outer product of two 1D spectra.

The Real Complexity

Naive 2D DFT. An $N \times N$ image has $N^2$ pixels and $N^2$ frequencies. Computing each output frequency directly requires summing over all $N^2$ input pixels: $O(N^4)$ operations in total. For a modest $1024 \times 1024$ image that is roughly $10^{12}$ multiplications — far too slow for interactive use.

The row-column (separable) algorithm. Because the 2D DFT factors as

X[k_1, k_2] = \sum_{n_1=0}^{N-1} \left( \sum_{n_2=0}^{N-1} x[n_1, n_2]\, e^{-2\pi i \frac{k_2 n_2}{N}} \right) e^{-2\pi i \frac{k_1 n_1}{N}},

you can compute the inner sum (a 1D DFT over each row) first, then the outer sum (a 1D DFT over each column of the result). Each of the $N$ rows costs $O(N \log N)$ with an FFT; so does each of the $N$ columns. Total: $O(N \cdot N \log N + N \cdot N \log N) = O(N^2 \log N)$ .

In $d$ dimensions. An $N^d$ volume requires $d \cdot N^{d-1}$ one-dimensional FFTs of length $N$ , giving $O(d \cdot N^d \log N)$ — or just $O(N^d \log N)$ when $d$ is fixed. The saving over the naive $O(N^{2d})$ approach grows exponentially with dimension.

Status: solved. The row-column decomposition was known before Cooley and Tukey (1965), but the FFT made it practically fast. FFTW (Frigo & Johnson, 1997) later showed that the optimal algorithm depends on the machine's cache hierarchy, not just the asymptotic count — auto-tuning at install time to find the best plan for each specific $N$ .

See also compression for how the related Discrete Cosine Transform (DCT) dominates image codecs, and pattern matching for how 2D convolution — equivalent to pointwise multiplication in frequency space — powers template search.

Where It Matters

The multidimensional FFT is one of the most widely deployed algorithms on the planet:

Image compression (JPEG/HEIC): the Discrete Cosine Transform — a close relative of the DFT — is applied to $8 \times 8$ pixel blocks. Low-frequency coefficients are kept; high-frequency ones are quantized away. The eye barely notices.
MRI reconstruction: a magnetic resonance scanner directly samples a 3D Fourier space (k-space). An inverse 3D FFT turns those raw measurements into a volumetric image.
Radio astronomy: interferometer arrays like the Very Large Array (VLA) and the Event Horizon Telescope measure the 2D Fourier transform of the sky. Imaging = inverse FFT.
Convolution in deep learning: large convolutional kernels are sometimes applied in frequency space — multiply the FFTs of the image and the filter, then inverse-FFT. When the kernel is big enough, $O(N^2 \log N)$ beats the $O(N^2 k^2)$ direct convolution.
Signal processing and radar: pulse compression, synthetic aperture radar (SAR), and sonar all exploit multidimensional FFTs to separate targets by range and Doppler shift.
Crystallography: X-ray diffraction patterns are the squared magnitudes of the 3D Fourier transform of electron density. Recovering the structure from diffraction data is (roughly) an inverse FFT — though the missing phase information makes it a genuinely hard problem.

The common thread: whenever a physical process mixes contributions linearly across space or time, the Fourier basis diagonalizes it — turning convolution into multiplication and turning hard global problems into cheap local ones in frequency space.

Conclusion

The multidimensional FFT is a triumph of mathematical structure exploited by algorithm design. The 2D DFT looks daunting — $N^4$ naive operations for an $N \times N$ image — but separability reveals that it is nothing more than $2N$ independent 1D problems, each solvable by the Cooley-Tukey FFT in $O(N \log N)$ . The saving is not a constant factor; it grows with $N$ and with the number of dimensions.

The same trick carries to three, four, and any number of dimensions without modification. Everything from your phone's camera pipeline to a hospital's MRI machine to a radio telescope array quietly runs on this one observation: the multidimensional Fourier transform separates along axes.

Draw a stripe, watch the spectrum snap to a perpendicular line, and you have seen the separability theorem with your own eyes. That perpendicular line is the whole story — repeated once per axis, at $O(N \log N)$ per pass, for as many dimensions as you need.

Comments

Loading comments...

https://www.kipuhub.com/en/article/fast-fourier-transform-ndim/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Multidimensional FFT

How separability turns a hard 2D problem into many easy 1D ones