Masanori Koyama

Harvey Mudd College Mathematics 2007

Thesis Proposal: Discrete Fourier Transform for Finite Groups
Thesis Report: mkoyama-2007-thesis.pdf
Thesis Poster: mkoyama-2007-poster.pdf
15 minutes Presentation:  15min_presentation.pdf
30 minutes Presentation:  mkoyama-2007-presentation
Thesis Advisor: Prof. Michael Orrison
Second Reader: Prof. Nathan Ryan

A Discrete Fourier Transform for Symmetric Group

A Discrete Fourier Transform (DFT) changes the basis in the Group Algebra from the standard basis to a Fourier basis, and efficient application of a DFT is called an Fast Fourier Transform (FFT). This research pertains to a particular algorithm of FFT called Decimation in Frequency (DIF). An efficient DIF has been established for commutative Algebra; however successful similar analogue for the non-commutative algebra has not been derived. In particular, sophisticated structure of the permutation bimodule has been deterring the computation of the runtime of a potentially fast DIF algorithm called Orrison-DIF. I will resolve this obstacle and compute
the general runtime of the algorithm for Symmetric group.