Matrix description of the fast Fourier transform
David K. Kahaner · IEEE Transactions on Audio and Electroacoustics · 1970
The fast Fourier transform is usually described as a factorization. Recently this has been done in matrix terms. In this paper we present these results in sufficient detail that interested nonexperts can obtain the computer algorithm, and the necessary label permutations. We also count the number of arithmetic operations required in the calculation and point out the well known utility of base 2, both because of mathematical and machine hardware considerations. A simple FORTRAN program based on these ideas is included.