Bidiagonal factorization of Fourier matrices and systolic algorithms for computing discrete Fourier transforms

An algorithm is presented for factoring Fourier matrices into products of bidiagonal matrices. These factorizations have the same structure for every n and make possible discrete Fourier transform (DFT) computation via a sequence of local, regular computations. A parallel pipeline technique for computing sequences of k-point DFTs, for every k⩽n, on a systolic array is proposed