The Discrete Fourier Transform via Circulants

摘要

The discrete Fourier Transform (DFT), defined below is a valuable tool in many fields from signal processing to partial differential equations. There is strong incentive for computing the transform quickly, and, after two decades of active research, we now know the minimum number of essential multiplications required for the task and have algorithms which use precisely this number. It does not follow that, in the end, these will be the most desirable techniques but they are certainly of interest in their own right. This story, and more, is told in the book.