Summary

This paper surveys algorithms for fast computation of convolution, comparing direct, FFT-based, and block-domain approaches and discussing optimizations for large-scale data. Readers will learn how algorithmic choices and parallel implementations affect complexity, memory use, and runtime in image, audio, and general DSP applications.

Key Takeaways

• Identify when to use direct time-domain convolution versus FFT-based block convolution based on signal/kernel sizes and complexity.
• Apply overlap-add and overlap-save block methods and choose FFT block sizes to balance latency, throughput, and memory.
• Exploit separability, symmetry, and kernel sparsity to reduce arithmetic and memory costs in spatial-domain convolution.
• Map convolution algorithms to parallel architectures (multicore CPUs, GPUs) to improve throughput while managing memory and I/O bottlenecks.
• Evaluate trade-offs between numerical accuracy, computational cost, and implementation complexity for large-scale or real-time DSP tasks.

Who Should Read This

DSP engineers, algorithm developers, and graduate students working on audio, image, radar, or communications systems who need to optimize convolution for large datasets or parallel hardware.

Still RelevantAdvanced

Topics