tailieunhanh - Fast Fourier Transform part 6

., electromagnetic or gravitational) on a three-dimensional lattice that represents the discretization of three-dimensional space. Here the source terms (mass or charge distribution) and | Fourier Transforms ofReal Data in Two and Three Dimensions 525 CITED REFERENCES AND FURTHER READING Nussbaumer . 1982 FastFourier TransformandConvolutionAlgorithms New York SpringerVerlag . Fourier Transforms ofReal Data in Two and Three Dimensions ilp g S. S o Z co cr q 2 v _ o ii 3 X-X Two-dimensional FFTs are particularly important in the field of image process- 9 ing. An image is usually represented as a two-dimensional array of pixel intensities I 1 g real and usually positive numbers. One commonly desires to filter high or low frequency spatial components from an image or to convolve or deconvolve the image with some instrumental point spread function. Use of the FFT is by far the most efficient technique. In three dimensions a common use of the FFT is to solve Poisson s equation a for a potential . electromagnetic or gravitational on a three-dimensional lattice i c that represents the discretization of three-dimensional space. Here the source terms mass or charge distribution and the desired potentials are also real. In two and three dimensions with large arrays memory is often at a premium. It is therefore important to perform the FFTs insofar as possible on the data in place. We want a routine with functionality similar to the multidimensional FFT routine fourn I jj o 3 but which operates on real not complex input data. We give such a routine in this section. The development is analogous to that of leading to . the one-dimensional routine realft. You might wish to review that material at z -g this point particularly equation . S g g- It is convenient to think of the independent variables n1 . nL in equation as representing an L-dimensional vector n in wave-number space with I 5 values on the lattice of integers. The transform H n . nL is then denoted 2 2 g H n . i S It is easy to see that the transform H n is periodic in each of its L dimensions. j . Specifically if P1 P2 P3 . denote the vectors N1 0 0 . 0 N2 0 . f 0