Convolution as an Algorithmic Speedup

Convolution as an Algorithmic Speedup (In-Class Demo)

In this in-class activity, we use a simple audio task to illustrate a core applied-algorithms idea:

A change in algorithm can matter far more than faster hardware or small optimizations.

The audio context is just motivation. The real goal is to understand convolution as a computational problem and see how the FFT turns an expensive method into a fast one.

What problem are we solving?

We have:

a long list of numbers representing an audio signal
a shorter list of numbers representing a filter (also called a kernel)

Filtering means producing a new list where each output value is a weighted sum of nearby input values. This operation is called convolution.

What is convolution?

At each position in the signal:

Line up the filter with the signal
Multiply corresponding values
Add them up

In code, this is just a sliding dot product.

If the signal has N samples and the filter has M taps, the naïve method does about:

$N \times M$

multiply-add operations.

Why the naïve approach becomes slow

For short filters, this is fine. But good-quality filters can have thousands of taps, and audio files can have millions of samples. That makes the naïve approach expensive.

This is not a constant-factor issue. It is an algorithmic complexity issue.

The key algorithmic idea (no FFT background required)

Up to this point, the problem is clear:

Filtering requires many repeated multiply-and-add operations
The naïve algorithm performs about N × M of them

At some point, this becomes too slow.

The question is:

Is there a different way to organize the same computation so we repeat less work?

The answer uses a standard algorithm called the Fast Fourier Transform (FFT).

You do not need to know how FFT works internally.

For our purposes, you can think of the FFT as a black box with this behavior:

It converts a long list of numbers into another list of numbers
In this new representation, convolution becomes simple multiplication
After multiplying, we convert back to the original representation

The important point is not what the FFT computes, but what it allows us to do efficiently.

Why this helps

The naïve convolution algorithm does:

$N \times M$

multiply-add operations.

The FFT-based method reorganizes the work so that the total cost is closer to:

$N \log N$

This is a fundamental algorithmic improvement, not a small optimization.

How to think about this (analogy)

Imagine multiplying two large numbers:

The grade-school method repeats a lot of small work
Better algorithms reorganize the computation to avoid repetition

FFT-based convolution does the same thing:

same result, different organization of work, much faster.

Why we use audio for this demonstration

Audio makes the task tangible:

Hiss is mostly high-frequency energy
A low-pass filter smooths the signal and reduces high-frequency content

You do not need advanced signal-processing knowledge for the algorithmic takeaway.

What we will do in class

Run naïve convolution on a real audio file and time it
Run FFT-based convolution on the same input and time it
Increase the filter length and observe how performance changes

Takeaways

This is a fundamental algorithmic speedup, not a micro-optimization

Convolution is structured repeated dot products

The naïve method repeats huge amounts of work

FFT-based convolution avoids that repetition