Date of Award

8-2008

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Legacy Department

Mathematical Science

Advisor

Gao, Shuhong

Committee Member

Brawley , Joel

Committee Member

Calkin , Neil

Committee Member

James , Kevin

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.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.