International
Tables for
Crystallography
Volume B
Reciprocal space
Edited by U. Shmueli

International Tables for Crystallography (2010). Vol. B, ch. 1.3, p. 52   | 1 | 2 |

Section 1.3.3.1. Introduction

G. Bricognea

aGlobal Phasing Ltd, Sheraton House, Suites 14–16, Castle Park, Cambridge CB3 0AX, England, and LURE, Bâtiment 209D, Université Paris-Sud, 91405 Orsay, France

1.3.3.1. Introduction

| top | pdf |

The Fourier transformation's most remarkable property is undoubtedly that of turning convolution into multiplication. As distribution theory has shown, other valuable properties – such as the shift property, the conversion of differentiation into multiplication by monomials, and the duality between periodicity and sampling – are special instances of the convolution theorem.

This property is exploited in many areas of applied mathematics and engineering (Campbell & Foster, 1948[link]; Sneddon, 1951[link]; Champeney, 1973[link]; Bracewell, 1986[link]). For example, the passing of a signal through a linear filter, which results in its being convolved with the response of the filter to a δ-function `impulse', may be modelled as a multiplication of the signal's transform by the transform of the impulse response (also called transfer function). Similarly, the solution of systems of partial differential equations may be turned by Fourier transformation into a division problem for distributions. In both cases, the formulations obtained after Fourier transformation are considerably simpler than the initial ones, and lend themselves to constructive solution techniques.

Whenever the functions to which the Fourier transform is applied are band-limited, or can be well approximated by band-limited functions, the discrete Fourier transform (DFT) provides a means of constructing explicit numerical solutions to the problems at hand. A great variety of investigations in physics, engineering and applied mathematics thus lead to DFT calculations, to such a degree that, at the time of writing, about 50% of all supercomputer CPU time is alleged to be spent calculating DFTs.

The straightforward use of the defining formulae for the DFT leads to calculations of size [N^{2}] for N sample points, which become unfeasible for any but the smallest problems. Much ingenuity has therefore been exerted on the design and implementation of faster algorithms for calculating the DFT (McClellan & Rader, 1979[link]; Nussbaumer, 1981[link]; Blahut, 1985[link]; Brigham, 1988[link]). The most famous is that of Cooley & Tukey (1965)[link] which heralded the age of digital signal processing. However, it had been preceded by the prime factor algorithm of Good (1958[link], 1960[link]), which has lately been the basis of many new developments. Recent historical research (Goldstine, 1977[link], pp. 249–253; Heideman et al., 1984[link]) has shown that Gauss essentially knew the Cooley–Tukey algorithm as early as 1805 (before Fourier's 1807 work on harmonic analysis!); while it has long been clear that Dirichlet knew of the basis of the prime factor algorithm and used it extensively in his theory of multiplicative characters [see e.g. Chapter I of Ayoub (1963)[link], and Chapters 6 and 8 of Apostol (1976)[link]]. Thus the computation of the DFT, far from being a purely technical and rather narrow piece of specialized numerical analysis, turns out to have very rich connections with such central areas of pure mathematics as number theory (algebraic and analytic), the representation theory of certain Lie groups and coding theory – to list only a few. The interested reader may consult Auslander & Tolimieri (1979)[link]; Auslander, Feig & Winograd (1982[link], 1984[link]); Auslander & Tolimieri (1985)[link]; Tolimieri (1985)[link].

One-dimensional algorithms are examined first. The Sande mixed-radix version of the Cooley–Tukey algorithm only calls upon the additive structure of congruence classes of integers. The prime factor algorithm of Good begins to exploit some of their multiplicative structure, and the use of relatively prime factors leads to a stronger factorization than that of Sande. Fuller use of the multiplicative structure, via the group of units, leads to the Rader algorithm; and the factorization of short convolutions then yields the Winograd algorithms.

Multidimensional algorithms are at first built as tensor products of one-dimensional elements. The problem of factoring the DFT in several dimensions simultaneously is then examined. The section ends with a survey of attempts at formalizing the interplay between algorithm structure and computer architecture for the purpose of automating the design of optimal DFT code.

It was originally intended to incorporate into this section a survey of all the basic notions and results of abstract algebra which are called upon in the course of these developments, but time limitations have made this impossible. This material, however, is adequately covered by the first chapter of Tolimieri et al. (1989)[link] in a form tailored for the same purposes. Similarly, the inclusion of numerous detailed examples of the algorithms described here has had to be postponed to a later edition, but an abundant supply of such examples may be found in the signal processing literature, for instance in the books by McClellan & Rader (1979)[link], Blahut (1985)[link], and Tolimieri et al. (1989)[link].

References

Apostol, T. M. (1976). Introduction to Analytic Number Theory. New York: Springer-Verlag.
Auslander, L., Feig, E. & Winograd, S. (1982). New algorithms for evaluating the 3-dimensional discrete Fourier transform. In Computational Crystallography, edited by D. Sayre, pp. 451–461. New York: Oxford University Press.
Auslander, L., Feig, E. & Winograd, S. (1984). Abelian semi-simple algebras and algorithms for the discrete Fourier transform. Adv. Appl. Math. 5, 31–55.
Auslander, L. & Tolimieri, R. (1979). Is computing with the finite Fourier transform pure or applied mathematics? Bull. Am. Math. Soc. 1, 847–897.
Auslander, L. & Tolimieri, R. (1985). Ring structure and the Fourier transform. Math. Intelligencer, 7, 49–54.
Ayoub, R. (1963). An Introduction to the Analytic Theory of Numbers. Providence: American Mathematical Society.
Blahut, R. E. (1985). Fast Algorithms for Digital Signal Processing. Reading: Addison-Wesley.
Bracewell, R. N. (1986). The Fourier Transform and its Applications, 2nd ed., revised. New York: McGraw-Hill.
Brigham, E. O. (1988). The Fast Fourier Transform and its Applications. Englewood Cliffs: Prentice-Hall.
Campbell, G. A. & Foster, R. M. (1948). Fourier Integrals for Practical Applications. Princeton: Van Nostrand.
Champeney, D. C. (1973). Fourier Transforms and their Physical Applications. New York: Academic Press.
Cooley, J. W. & Tukey, J. W. (1965). An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19, 297–301.
Goldstine, H. H. (1977). A History of Numerical Analysis From the 16th Through the 19th Century. New York: Springer-Verlag.
Good, I. J. (1958). The interaction algorithm and practical Fourier analysis. J. R. Stat. Soc. B20, 361–372.
Good, I. J. (1960). Addendum [to Good (1958)]. J. R. Stat. Soc. B22, 372–375.
Heideman, M. T., Johnson, D. H. & Burrus, C. S. (1984). Gauss and the history of the fast Fourier transform. IEEE Acoust. Speech Signal Process. Mag. October 1984.
McClellan, J. H. & Rader, C. M. (1979). Number Theory in Digital Signal Processing. Englewood Cliffs: Prentice Hall.
Nussbaumer, H. J. (1981). Fast Fourier Transform and Convolution Algorithms. Berlin: Springer-Verlag.
Sneddon, I. N. (1951). Fourier Transforms. New York: McGraw-Hill.
Tolimieri, R. (1985). The algebra of the finite Fourier transform and coding theory. Trans. Am. Math. Soc. 287, 253–273.
Tolimieri, R., An, M. & Lu, C. (1989). Algorithms for Discrete Fourier Transform and Convolution. New York: Springer-Verlag.








































to end of page
to top of page