Area-time complexity for VLSI

TLDR

The study investigates the computational complexity of the Discrete Fourier Transform within a VLSI‑appropriate model. The model evaluates DFT implementations by jointly considering the silicon area and the execution time required on a single chip. The authors prove that for any chip design the product of area and time squared satisfies AT² ≥ N²/16, and more generally AT^x = Ω(N^{1+x/2}) for 0 ≤ x ≤ 2, with the bound nearly tight when T = Θ(N^{1/2}) or T = Θ(log N).

Abstract

The complexity of the Discrete Fourier Transform (DFT) is studied with respect to a new model of computation appropriate to VLSI technology. This model focuses on two key parameters, the amount of silicon area and time required to implement a DFT on a single chip. Lower bounds on area (A) and time (T) are related to the number of points (N) in the DFT: AT2≥ N2/16. This inequality holds for any chip design based on any algorithm, and is nearly tight when T = θ(N1/2) or T = θ(log N). A more general lower bound is also derived: ATx = Ω(N1+x/2), for 0≤×≤2.