Convolutions in the Fourier domain

What does the contact area of two stiff objects look like when they are pressed against each other and how large is the force? The Dutch company VORtech uses a software package called CONTACT to answer such questions, which involves a lot of convolution operations. This work shows how convolutions between matrices can be performed much faster by using a technique called `fast Fourier transform'. The first part provides a theoretical explanation of Fourier transforms and convolutions. Barrowes' method for computing the product of a matrix of a specific form with a vector is also explained since it is closely related to convolutions. In the second part, the performance of the standard convolution method is compared to Barrowes' method and the fast Fourier transform method, regarding both memory usage and run time. Implementation details using the Intel Math Kernel Library are also given. Experiments show that using fast Fourier transforms can result in significant speed-ups. Possible optimizations are explained and tested, which results in a few general recommendations for using fast Fourier transforms optimally.