| Home > Publications > Reports > Numerical Analysis and Applied Mathematics (TW) |
TW 481
Steven Delvaux, Marc Van Barel
FFT-like factorizations using group theory
Abstract
The Fast Fourier Transform (FFT) is based on an important factorization of the Fourier matrix Fn into a product of sparse matrices. In this paper, we demonstrate the existence of a set of FFT-like factorizations for an arbitrary Kronecker product of Fourier matrices F = Fn1⊗ ... ⊗ Fnk. We show that there exists such a factorization for any chain of nested subgroups of the Abelian group Zn1× ... × Znk. The classical FFT will then be a special case of this scheme. However, the construction of FFT-like factorizations will allow a lot of freedom. This will allow to construct factorizations which cannot be obtained by simply inserting the classical FFT of each of the Kronecker factors of F. It will also be shown that the FFT-like factorizations of the matrix F can be brought into correspondence with the partitions of F into nested grids of rank-one blocks.
report.pdf (386K) / mailto: M. Van Barel