BSc Thesis Defense by Hans Jacob Teglbjærg Stephensen

Abstract:

In this project, I show how convolutions can be computed efficiently using the Fast Fourier Transform (FFT). I explain the theory that makes FFT possible and present an implementation, which can be incorporated into to the SHARK Machine Learning Library. Being a low level algorithm consisting of many small mathematical operations, I show how both reduc- tions in computational complexity and specific low level optimizations lead to a considerable reduction in execution time. Different methods for computing the convolution exist, and I show how it is possible to implement a mechanism to switch between methods. I conclude that my implementation works and is asymptotically efficient, but that much more work is needed for the efficiency to compete with state-of-the-art implementations. An alternative approach using the FFTW library is therefore presented.

Supervisor: Christian Igel
Censor: Ole Winther, DTU