Effective implementation of fast convolution

Effective implementation of fast convolution using by fourier transform. Overlap-add and overlap-save methods are used.

This is an effective implementation of 2d convolution using the Fourier transform combined together with over-save and over-add approaches. In general, a standard convolution computed in spatial domain is a time consuming process. Vice versa, the computation in frequency domain is space-intensive. The aim of our implementation is to find a solution that is able to perform the convolution over large data (both signal and kernel) in a reasonably short time while using a limited amount of memory.

The implementation first splits the kernel and signal into the same large rectangular tiles and subsequently performs the convolution in frequency domain over these smaller memory blocks. The splitting process is based on the overlap-add method and overlap-save methods that chop kernel and signal, respectively.

The current implementation works in two dimensions, but the best use of this approach can be expected when handling the large data in three or more dimensions (currently in progress). There is no constrain put on the kernel properties. It works well with separable as well as with non-separable kernels. For large data and non-separable kernels, it performs even better than the standard „conv2“ function. You can try our implementation by running the script „example.m“.