In these algorithms, the 1D and the 2D discrete Fourier transform (DFT) matrices are factorized into the Kronecker product of DFT matrices of smaller size. The architectures consist of 2D grid of processing elements with temporal and spatial locality of connections. For implementing the 1D-DFT of size \(N\) or the 2D-DFT of size \(\sqrt N\) by \(\sqrt N\), \(2N\) multipliers and adders are necessary. As for their complexity, it takes approximately \(2\sqrt N\) steps of mathematical operations for computing the transform vector and approximately \(\sqrt N\) steps for computing between two successive transform vectors.