00 Acta Scientific | International Open Library | Open Access Journals Publishing Group

Acta Scientific Computer Sciences

Review Article Volume 3 Issue 1

Parallel Fast-fourier Transform

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

Reprints View PDF Related Articles

×

Abstract

  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

×

References

  1. A Dubey., et al. “A general purpose subroutine for Fast Fourier Transform on a distributed memory parallel machine”. Parallel Computing 20 (1994): 1697-1710.
  2. Shuhong Gao and Todd Mateer. “Additive Fast Fourier Transforms over Finite Fields”.
  3. Bo Liu. “Parallel Fast Fourier Transform, 159.735 Studies in Parallel and Distributed System”
  4. Brigham EO. “The fast Fourier transform and its applications”. Englewood Cliffs, N, J.: Prentice Hall (1988).
  5. C Van Loan. Computational Frameworks for the Fast Fourier Transform, SIAM, Philadelphia, PA, (1992).
  6. Chu E and George A. FFT algorithms and their adaptation to parallel processing, Linear Algebra and its Applications 284 (1998).
  7. Chu E and George A. “Inside the FFT black box: serial and parallel fast Fourier transform algorithms”. Boca Raton, Fla.: CRC Press (1999).
  8. Gray RM and Goodman JW. “Fourier transforms: an introduction for engineers”. Boston: Kluwer Academic Publishers (1995).
  9. Herbert Karner and Christoph W Ueberhuber. Parallel FFT algorithms with reduced communication overhead, Institute for Applied and Numerical Mathematics, Technical University of Vienna
  10. M C Pease. “An adaptation of the fast Fourier transform for parallel processing”. Journal of the ACM2 (1968): 252-264.
  11. Matteo Frigo., et al. Cache- Oblivious Algorithms, MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA 02139.
  12. Michael Balducci., et al. “Comparative Analysis of FFT algorithms in sequential and parallel form”. Mississippi State University.
  13. P N Swarztrauber. “Multiprocessor FFTs”. Parallel Computing 5 (1987): 197-210.
  14. Quinn MJ. “Parallel programming in C with MPI and OpenMP”. New York: McGraw-Hill Higher Education (2004).
  15. Somasundaram Meiyappan, Implementation and performance evaluation of parallel FFT algorithms, School of Computing National University of Singapore.
  16. W L Briggs and V E Henson. The DFT: An Owner’s Manual for the Discrete Fourier Transform, SIAM, Philadelphia, PA (1995).
  17. W Yang. “Parallel ordered FFT algorithms on distributed-memory multiprocessors”. M.Sc. Thesis, Department of Mathematics and Statistics, University of Guelph, Guelph, Ontario (1996).
×

Citation

Citation: Ola Nadim Halawi. “Parallel Fast-fourier Transform”. Acta Scientific Computer Sciences 3.2 (2021): 17-30.




Metrics

Acceptance rate35%
Acceptance to publication20-30 days

Indexed In




News and Events


  • Certification for Review
    Acta Scientific certifies the Editors/reviewers for their review done towards the assigned articles of the respective journals.
  • Submission Timeline for Upcoming Issue
    The last date for submission of articles for regular Issues is November 25, 2024.
  • Publication Certificate
    Authors will be issued a "Publication Certificate" as a mark of appreciation for publishing their work.
  • Best Article of the Issue
    The Editors will elect one Best Article after each issue release. The authors of this article will be provided with a certificate of "Best Article of the Issue"
  • Welcoming Article Submission
    Acta Scientific delightfully welcomes active researchers for submission of articles towards the upcoming issue of respective journals.

Contact US





+91 9182824667

     info@acta-scientific.com

Creative Commons License Open Access by Acta Scientific is licensed under a Creative Commons Attribution 4.0 International License
Based on a work at https://actascientific.com

ff

Acta-Publications

ff

© 2021 Acta Scientific, All rights reserved.