A new method mathematically links fast Fourier transform algorithms with fast cyclic convolution algorithms

摘要

The cyclic convolution theorem is used to formally link certain factorizations of the DFT matrix to factorizations of the circulant matrices. As an example, the DFT matrix decomposition leading to the decimation in time fast Fourier transform is mathematically linked to a circulant matrix decomposition, which in turn leads to a fast cyclic convolution algorithm. Most importantly, permutations of the DFT matrix are shown to be related to permutations of the circulant matrices. It is therefore illustrated how certain factorizations, in one domain, could lead to fast algorithms in both domains, thus, providing further insight and needed unification.