Fast Jacket transform for DFT matrices based on prime factor algorithm

Underlying the prime factor algorithm (PFA) employed Chinese remainder theorem (CRT), one-dimensional DFT can be mapped to the true two-dimensional DFT avoid twiddle factors. Enlighten by the idea of fast Jacket transform, a simple construction for large size DFT matrices is proposed. Based on the multi-dimensional index mapping extended from two-dimensional case, a general approach to decompose multi-dimensional DFT matrices is described in simple manner. The proposed algorithms are presented for simplicity and clarity for it only minimally related to sparse matrices. The results indicate the presented fast algorithms compare favourably with direct computation.