Discrete and Fast Fourier Transform Made Clear

arXiv1908.07154MaRDI QIDQ6323910FDOQ6323910

Publication date: 17 August 2019

Abstract: Fast Fourier transform was included in the Top 10 Algorithms of 20th Century by Computing in Science & Engineering. In this paper, we provide a new simple derivation of both the discrete Fourier transform and fast Fourier transform by means of elementary linear algebra. We start the exposition by introducing the convolution product of vectors, represented by a circulant matrix, and derive the discrete Fourier transform as the change of basis matrix that diagonalizes the circulant matrix. We also generalize our approach to derive the Fourier transform on any finite abelian group, where the case of Fourier transform on the Boolean cube is especially important for many applications in theoretical computer science.

This page was built for publication: Discrete and Fast Fourier Transform Made Clear

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6323910)