A very large class of important computational problems falls under the general rubric of “Fourier transform methods” or “spectral methods.” For some of these problems, the Fourier transform is simply an efficient computational tool for accomplishing certain common manipulations of data. | Chapter 12. Fast Fourier Transform Introduction A very large class of important computational problems falls under the general rubric of Fourier transform methods or spectral methods. For some of these problems the Fourier transform is simply an efficient computational tool for accomplishing certain common manipulations of data. In other cases we have problems for which the Fourier transform or the related power spectrum is itself of intrinsic interest. These two kinds of problems share a common methodology. Largely for historical reasons the literature on Fourier and spectral methods has been disjointfrom the literature on classical numerical analysis. Nowadays there is no justificationfor such a split. Fourier methods are commonplace in research and we shall not treat them as specialized or arcane. At the same time we realize that many computer users have had relatively less experience with this field than with say differential equations or numerical integration. Therefore our summary of analytical results will be more complete. Numerical algorithms per se begin in . Various applications of Fourier transform methods are discussed in Chapter 13. A physical process can be described either in the time domain by the values of some quantity h as a function of time t . h t or else in the frequency domain where the process is specified by giving its amplitude H generally a complex number indicating phase also as a function of frequency f that is H f with 1 f 1. For many purposes it is useful to think of h t and H f as being two different representations of the same function. One goes back and forthbetween these two representations by means of the Fourier transform equations H f hft e2fdt J11 h t h f - f df If t is measured in seconds then f in equation is in cycles per second or Hertz the unit of frequency . However the equations work with other units too. If h is a function of position x in meters H will be a function of inverse wavelength .
