Constant geometry fast Fourier transforms on array processors

Matrix algebra is used to design and validate parallel algorithms for large constant-geometry fast Fourier transforms (FFTs) on fixed-size array processors. The N-point radix 2 case for a linear array processor with N/2 cells is identical to the usual procedure corresponding to the matrix factorization of M.C. Pease, (1968). The algorithms are engendered by matrix factorizations, which themselves depend on a basic factorization of the perfect shuffle. The resulting data movement is realized in parallel as relatively small perfect shuffles inside each local memory and along each row and column of the array processor, without requiring that the complete array itself have the shuffle-exchange network