Ola Nadim Halawi*
Department of Computer Science, Lebanon
*Corresponding Author: Ola Nadim Halawi, Department of Computer Science, Lebanon.
Received: November 30, 2020; Published: January 22, 2021
The Fast Fourier Transform (FFT) is an algorithm that is used to compute the Discrete Fourier Transform (DFT) of N points. It is extensively applied in many domains that make use of sinusoidal signals. Some of the well-known FFT algorithms include Radix-2, Radix-4, and Split Radix algorithms, their time complexity is O (n log n). The Fourier Transform algorithm is computationally intensive since it includes many additions, multiplications, and trigonometric functions. Thus, parallelizing the serial FFT algorithms would be very advantageous in terms of code complexity and execution time. This paper aims to provide a means for users to efficiently perform FFT of a polynomial over a finite field, and discusses ways of parallelizing FFT to reduce the communication overhead. Cache-oblivious sub-routines will be used to minimize page faults incurred regardless of the underlying cache-hierarchy, and parallelization will serve in reducing the real time needed by the algorithm. Also, the user will be able to compute the discrete Taylor expansion of a polynomial in a finite field (this functionality is a prerequisite to being able to compute the FFT). To achieve this, a data type will be provided for the user so that he/she can easily input the required polynomial. The project will use Open MPI directives to allow some of the program’s segments to run in parallel in order to speed up the computation process. While this provides an efficient parallelized FFT, there is a significant communication overhead that should be considered.
Keywords: Fast Fourier Transform (FFT); Discrete Fourier Transform (DFT); Algorithm
Citation: Ola Nadim Halawi. “Parallel Fast-fourier Transform”. Acta Scientific Computer Sciences 3.2 (2021): 17-30.
Copyright: © 2021 Ola Nadim Halawi. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.