Back to search

Clemson University

Fast Fourier Transform Algorithms with Applications

Abstract

dc:description.abstract

This manuscript describes a number of algorithms that can be used to quickly evaluate a polynomial over a collection of points and interpolate these evaluations back into a polynomial. Engineers define the 'Fast Fourier Transform' as a method of solving the interpolation problem where the coefficient ring used to construct the polynomials has a special multiplicative structure. Mathematicians define the 'Fast Fourier Transform' as a method of solving the evaluation problem. One purpose of the document is to provide a mathematical treatment of the topic of the 'Fast Fourier Transform' that can also be understood by someone who has an understanding of the topic from the engineering perspective. The manuscript will also introduce several new algorithms that solve the fast multipoint evaluation problem over certain finite fields and require fewer finite field operations than existing techniques. The document will also demonstrate that these new algorithms can be used to multiply polynomials with finite field coefficients with fewer operations than Schonhage's algorithm in most circumstances. A third objective of this document is to provide a mathematical perspective of several algorithms which can be used to multiply polynomials of size which is not a power of two. Several improvements to these algorithms will also be discussed. Finally, the document will describe several applications of the 'Fast Fourier Transform' algorithms presented and will introduce improvements in several of these applications. In addition to polynomial multiplication, the applications of polynomial division with remainder, the greatest common divisor, decoding of Reed-Solomon error-correcting codes, and the computation of the coefficients of a discrete Fourier Series will be addressed.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (PhD)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Mathematical Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Mateer, Todd
Contributors dc:contributor
  • Gao, Shuhong
  • Brawley , Joel
  • Calkin , Neil
  • James , Kevin

Subjects

dc:subject × 7

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_dissertations/231

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Mateer, Todd. Fast Fourier Transform Algorithms with Applications. Dissertation thesis, https://open.clemson.edu/all_dissertations/231