New Area-Time Lower Bounds for the Multidimensional DFT

Area-time lower bounds are derived for the VLSI computation of the (n1 x n2 x ... nd)-point multidimensional DFT (MDDFT) over different types of rings and different types of input/output protocols. First, an AT^2 = Ω((N log|R|)^2) bound is obtained for any finite ring R, where N = n1 x n2 x ... x nd, for any word-local protocol. The bound was previously known for the special case when R = Z_M, the ring of integers modulo M. Second, an AT^2 = Ω((Nb)^2) word-local bound is derived when R is the complex field, the components of the input are fixed-point numbers of b bits, and the precision of the output components guarantees that the resulting approximate transform is injective. No area-time lower bound was previously known for the DFT over the complex field. Third, an AT^2 = Ω((N log|R|)^2) bound is derived when R = GF(p^m) is a finite field of polynomials of degree m with coefficients in Z_p, for certain classes of non word-local protocols. This is the first area-time lower bound derived for the DFT with I/O protocols that are not word-local.