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.