Graduation Year
2005
Document Type
Open Access Senior Thesis
Degree Name
Bachelor of Science
Department
Mathematics
Reader 1
Michael Orrison
Reader 2
Weiqing Gu
Abstract
In this thesis, we present a new class of algorithms that determine fast Fourier transforms for a given finite group G. These algorithms use eigenspace projections determined by a chain of subgroups of G, and rely on a path algebraic approach to the representation theory of finite groups developed by Ram (26). Applying this framework to the symmetric group, Sn, yields a class of fast Fourier transforms that we conjecture to run in O(n2n!) time. We also discuss several future directions for this research.
Recommended Citation
Malm, Eric, "Decimation-in-Frequency Fast Fourier Transforms for the Symmetric Group" (2005). HMC Senior Theses. 173.
https://scholarship.claremont.edu/hmc_theses/173
Thesis Proposal
emalm-2004-10-12-ffts.pdf (605 kB)
10-Minute Thesis Presentation
emalm-2004-11-23-ffts.pdf (309 kB)
20-Minute Thesis Presentation
emalm-2005-01-08-ffts.pdf (231 kB)
DIF FFTs for the Symmetric Group
emalm-2005-04-17-ffts.pdf (245 kB)
Admitted Students Program
emalm-2005-05-02-ffts.pdf (414 kB)
Presentation Days Slides
emalm-2005-thesis-poster.pdf (275 kB)
Presentation Days Poster
emalm-2005-annbib.pdf (67 kB)
Bibliography
emalm-2005-expository.pdf (197 kB)
Recent Results in General FFTs
emalm-2005-midyear.pdf (429 kB)
Midyear Report
emalm-2005-prob-statement.pdf (30 kB)
Problem Statement
eric-malm-picture.jpg (26 kB)
Picture of Eric Malm
