International
Tables for Crystallography Volume B Reciprocal space Edited by U. Shmueli © International Union of Crystallography 2006 
International Tables for Crystallography (2006). Vol. B, ch. 1.3, pp. 7172

In 1929, W. L. Bragg demonstrated the practical usefulness of the Fourier transform relation between electron density and structure factors by determining the structure of diopside from three principal projections calculated numerically by 2D Fourier summation (Bragg, 1929). It was immediately realized that the systematic use of this powerful method, and of its extension to three dimensions, would entail considerable amounts of numerical computation which had to be organized efficiently. As no other branch of applied science had yet needed this type of computation, crystallographers had to invent their own techniques.
The first step was taken by Beevers & Lipson (1934) who pointed out that a 2D summation could be factored into successive 1D summations. This is essentially the tensor product property of the Fourier transform (Sections 1.3.2.4.2.4, 1.3.3.3.1), although its aspect is rendered somewhat complicated by the use of sines and cosines instead of complex exponentials. Computation is economized to the extent that the cost of an transform grows with N as rather than . Generalization to 3D is immediate, reducing computation size from to for an transform. The complication introduced by using expressions in terms of sines and cosines is turned to advantage when symmetry is present, as certain families of terms are systematically absent or are simply related to each other; multiplicity corrections must, however, be introduced. The necessary information was tabulated for each space group by Lonsdale (1936), and was later incorporated into Volume I of International Tables.
The second step was taken by Beevers & Lipson (1936) and Lipson & Beevers (1936) in the form of the invention of the `Beevers–Lipson strips', a practical device which was to assist a whole generation of crystallographers in the numerical computation of crystallographic Fourier sums. The strips comprise a set of `cosine strips' tabulating the functions and a set of `sine strips' tabulating the functions for the 16 arguments . Function values are rounded to the nearest integer, and those for other arguments m may be obtained by using the symmetry properties of the sine and cosine functions. A Fourier summation of the form is then performed by selecting the n cosine strips labelled and the n sine strips labelled , placing them in register, and adding the tabulated values columnwise. The number 60 was chosen as the l.c.m. of 12 (itself the l.c.m. of the orders of all possible nonprimitive translations) and of 10 (for decimal convenience). The limited accuracy imposed by the twodigit tabulation was later improved by Robertson's sorting board (Robertson, 1936a,b) or by the use of separate strips for each decimal digit of the amplitude (Booth, 1948b), which allowed threedigit tabulation while keeping the set of strips within manageable size. Cochran (1948a) found that, for most structures under study at the time, the numerical inaccuracies of the method were less than the level of error in the experimental data. The sampling rate was subsequently increased from 60 to 120 (Beevers, 1952) to cope with larger unit cells.
Further gains in speed and accuracy were sought through the construction of specialpurpose mechanical, electromechanical, electronic or optical devices. Two striking examples are the mechanical computer RUFUS built by Robertson (1954, 1955, 1961) on the principle of previous strip methods (see also Robertson, 1932) and the electronic analogue computer XRAC built by Pepinsky, capable of realtime calculation and display of 2D and 3D Fourier syntheses (Pepinsky, 1947; Pepinsky & Sayre, 1948; Pepinsky et al., 1961; see also Suryan, 1957). The optical methods of Lipson & Taylor (1951, 1958) also deserve mention. Many other ingenious devices were invented, whose descriptions may be found in Booth (1948b), Niggli (1961), and Lipson & Cochran (1968).
Later, commercial punchedcard machines were programmed to carry out Fourier summations or structurefactor calculations (Shaffer et al., 1946a,b; Cox et al., 1947, 1949; Cox & Jeffrey, 1949; Donohue & Schomaker, 1949; Grems & Kasper, 1949; Hodgson et al., 1949; Greenhalgh & Jeffrey, 1950; Kitz & Marchington, 1953).
The modern era of digital electronic computation of Fourier series was initiated by the work of Bennett & Kendrew (1952), Mayer & Trueblood (1953), Ahmed & Cruickshank (1953b), Sparks et al. (1956) and Fowweather (1955). Their Fouriersynthesis programs used Beevers–Lipson factorization, the program by Sparks et al. being the first 3D Fourier program useable for all space groups (although these were treated as P1 or by data expansion). Ahmed & Barnes (1958) then proposed a general programming technique to allow full use of symmetry elements (orthorhombic or lower) in the 3D Beevers–Lipson factorization process, including multiplicity corrections. Their method was later adopted by Shoemaker & Sly (1961), and by crystallographic program writers at large.
The discovery of the FFT algorithm by Cooley & Tukey in 1965, which instantly transformed electrical engineering and several other disciplines, paradoxically failed to have an immediate impact on crystallographic computing. A plausible explanation is that the calculation of large 3D Fourier maps was a relatively infrequent task which was not thought to constitute a bottleneck, as crystallographers had learned to settle most structural questions by means of cheaper 2D sections or projections. It is significant in this respect that the first use of the FFT in crystallography by Barrett & Zwick (1971) should have occurred as part of an iterative scheme for improving protein phases by density modification in real space, which required a much greater number of Fourier transformations than any previous method. Independently, Bondot (1971) had attracted attention to the merits of the FFT algorithm.
The FFT program used by Barrett & Zwick had been written for signalprocessing applications. It was restricted to sampling rates of the form , and was not designed to take advantage of crystallographic symmetry at any stage of the calculation; Bantz & Zwick (1974) later improved this situation somewhat.
It was the work of Ten Eyck (1973) and Immirzi (1973, 1976) which led to the general adoption of the FFT in crystallographic computing. Immirzi treated all space groups as P1 by data expansion. Ten Eyck based his program on a versatile multiradix FFT routine (Gentleman & Sande, 1966) coupled with a flexible indexing scheme for dealing efficiently with multidimensional transforms. He also addressed the problems of incorporating symmetry elements of order 2 into the factorization of 1D transforms, and of transposing intermediate results by other symmetry elements. He was thus able to show that in a large number of space groups (including the 74 space groups having orthorhombic or lower symmetry) it is possible to calculate only the unique results from the unique data within the logic of the FFT algorithm. Ten Eyck wrote and circulated a package of programs for computing Fourier maps and reanalysing them into structure factors in some simple space groups (P1, P1, P2, P2/m, P2_{1}, P222, P2_{1}2_{1}2_{1}, Pmmm). This package was later augmented by a handful of new spacegroupspecific programs contributed by other crystallographers (P2_{1}2_{1}2, I222, P3_{1}21, P4_{1}2_{1}2). The writing of such programs is an undertaking of substantial complexity, which has deterred all but the bravest: the usual practice is now to expand data for a highsymmetry space group to the largest subgroup for which a specific FFT program exists in the package, rather than attempt to write a new program. Attempts have been made to introduce more modern approaches to the calculation of crystallographic Fourier transforms (Auslander, Feig & Winograd, 1982; Auslander & Shenefelt, 1987; Auslander et al., 1988) but have not gone beyond the stage of preliminary studies.
The task of fully exploiting the FFT algorithm in crystallographic computations is therefore still unfinished, and it is the purpose of this section to provide a systematic treatment such as that (say) of Ahmed & Barnes (1958) for the Beevers–Lipson algorithm.
Ten Eyck's approach, based on the reducibility of certain space groups, is extended by the derivation of a universal transposition formula for intermediate results. It is then shown that space groups which are not completely reducible may nevertheless be treated by threedimensional Cooley–Tukey factorization in such a way that their symmetry may be fully exploited, whatever the shape of their asymmetric unit. Finally, new factorization methods with builtin symmetries are presented. The unifying concept throughout this presentation is that of `group action' on indexing sets, and of `orbit exchange' when this action has a composite structure; it affords new ways of rationalizing the use of symmetry, or of improving computational speed, or both.
References
Ahmed, F. R. & Barnes, W. H. (1958). Generalized programmes for crystallographic computations. Acta Cryst. 11, 669–671.Ahmed, F. R. & Cruickshank, D. W. J. (1953b). Crystallographic calculations on the Manchester University electronic digital computer (Mark II). Acta Cryst. 6, 765–769.
Auslander, L., Feig, E. & Winograd, S. (1982). New algorithms for evaluating the 3dimensional discrete Fourier transform. In Computational crystallography, edited by D. Sayre, pp. 451–461. New York: Oxford University Press.
Auslander, L., Johnson, R. W. & Vulis, M. (1988). Evaluating finite Fourier transforms that respect group symmetries. Acta Cryst. A44, 467–478.
Auslander, L. & Shenefelt, M. (1987). Fourier transforms that respect crystallographic symmetries. IBM J. Res. Dev. 31, 213–223.
Bantz, D. & Zwick, M. (1974). The use of symmetry with the fast Fourier algorithm. Acta Cryst. A30, 257–260.
Barrett, A. N. & Zwick, M. (1971). A method for the extension and refinement of crystallographic protein phases utilizing the fast Fourier transform. Acta Cryst. A27, 6–11.
Beevers, C. A. (1952). Fourier strips at a 3° interval. Acta Cryst. 5, 670–673.
Beevers, C. A. & Lipson, H. (1934). A rapid method for the summation of a twodimensional Fourier series. Philos. Mag. 17, 855–859.
Beevers, C. A. & Lipson, H. (1936). A numerical method for twodimensional Fourier synthesis. Nature (London), 137, 825–826.
Bennett, J. M. & Kendrew, J. C. (1952). The computation of Fourier syntheses with a digital electronic calculating machine. Acta Cryst. 5, 109–116.
Bondot, P. (1971). Application de la transformée de Fourier performante aux calculs cristallographiques. Acta Cryst. A27, 492–494.
Booth, A. D. (1948b). Fourier technique in Xray organic structure analysis. Cambridge University Press.
Bragg, W. L. (1929). Determination of parameters in crystal structures by means of Fourier series. Proc. R. Soc. London Ser. A, 123, 537–559.
Cochran, W. (1948a). A critical examination of the Beevers–Lipson method of Fourier series summation. Acta Cryst. 1, 54–56.
Cox, E. G., Gross, L. & Jeffrey, G. A. (1947). A Hollerith punchedcard method for the evaluation of electron density in crystal structure analysis. Proc. Leeds Philos. Soc. 5, 1–13.
Cox, E. G., Gross, L. & Jeffrey, G. A. (1949). A Hollerith technique for computing threedimensional differential Fourier syntheses in Xray crystal structure analysis. Acta Cryst. 2, 351–355.
Cox, E. G. & Jeffrey, G. A. (1949). The use of Hollerith computing equipment in crystal structure analysis. Acta Cryst. 2, 341–343.
Donohue, J. & Schomaker, V. (1949). The use of punched cards in molecular structure determinations. III. Structure factor calculations of Xray crystallography. Acta Cryst. 2, 344–347.
Fowweather, F. (1955). The use of general programmes for crystallographic calculations on the Manchester University electronic digital computer (Mark II). Acta Cryst. 8, 633–637.
Gentleman, W. M. & Sande, G. (1966). Fast Fourier transforms – for fun and profit. In AFIPS Proc. 1966 Fall Joint Computer Conference, pp. 563–578. Washington, DC: Spartan Books.
Greenhalgh, D. M. S. & Jeffrey, G. A. (1950). A new punched card method of Fourier synthesis. Acta Cryst. 3, 311–312.
Grems, M. D. & Kasper, J. S. (1949). An improved punchedcard method for crystal structurefactor calculations. Acta Cryst. 2, 347–351.
Hodgson, M. L., Clews, C. J. B. & Cochran, W. (1949). A punched card modification of the Beevers–Lipson method of Fourier synthesis. Acta Cryst. 2, 113–116.
Immirzi, A. (1973). A general Fourier program for Xray crystalstructure analysis which utilizes the Cooley–Tukey algorithm. J. Appl. Cryst. 6, 246–249.
Immirzi, A. (1976). Fast Fourier transform in crystallography. In Crystallographic computing techniques, edited by F. R. Ahmed, pp. 399–412. Copenhagen: Munksgaard.
Kitz, N. & Marchington, B. (1953). A method of Fourier synthesis using a standard Hollerith senior rolling total tabulator. Acta Cryst. 6, 325–326.
Lipson, H. & Beevers, C. A. (1936). An improved numerical method of twodimensional Fourier synthesis for crystals. Proc. Phys. Soc. London, 48, 772–780.
Lipson, H. & Cochran, W. (1968). The determination of crystal structures. Revised and enlarged edition. London: G. Bell & Sons.
Lipson, H. & Taylor, C. A. (1951). Optical methods in Xray analysis. II. Fourier transforms and crystalstructure determination. Acta Cryst. 4, 458–462.
Lipson, H. & Taylor, C. A. (1958). Fourier transforms and Xray diffraction. London: Bell.
Lonsdale, K. (1936). Simplified structure factor and electron density formulae for the 230 space groups of mathematical crystallography. London: Bell.
Mayer, S. W. & Trueblood, K. N. (1953). Threedimensional Fourier summations on a highspeed digital computer. Acta Cryst. 6, 427.
Niggli, A. (1961). Smallscale computers in Xray crystallography. In Computing methods and the phase problem, edited by R. Pepinsky, J. M. Robertson & J. C. Speakman, pp. 12–20. Oxford: Pergamon Press.
Pepinsky, R. (1947). An electronic computer for Xray crystal structure analyses. J. Appl. Phys. 18, 601–604.
Pepinsky, R., van den Hende, J. & Vand, V. (1961). XRAC and digital computing methods. In Computing methods and the phase problem, edited by R. Pepinsky, J. M. Robertson & J. C. Speakman, pp. 154–160. Oxford: Pergamon Press.
Pepinsky, R. & Sayre, D. (1948). Quantitative electrondensity contour delineation in the electronic Fourier synthesizer for crystal structure analysis. Nature (London), 162, 22–23.
Robertson, J. M. (1932). A simple harmonic continuous calculating machine. Philos. Mag. 13, 413–419.
Robertson, J. M. (1936a). Numerical and mechanical methods in double Fourier synthesis. Philos. Mag. 21, 176–187.
Robertson, J. M. (1936b). Calculation of structure factors and summation of Fourier series in crystal analysis: noncentrosymmetrical projections. Nature (London), 138, 683–684.
Robertson, J. M. (1954). A fast digital computer for Fourier operations. Acta Cryst. 7, 817–822.
Robertson, J. M. (1955). Some properties of Fourier strips with applications to the digital computer. Acta Cryst. 8, 286–288.
Robertson, J. M. (1961). A digital mechanical computer for Fourier operations. In Computing methods and the phase problem, edited by R. Pepinsky, J. M. Robertson & J. C. Speakman, pp. 21–24. Oxford: Pergamon Press.
Shaffer, P. A. Jr, Schomaker, V. & Pauling, L. (1946a). The use of punched cards in molecular structure determinations. I. Crystal structure calculations. J. Chem. Phys. 14, 648–658.
Shaffer, P. A. Jr, Schomaker, V. & Pauling, L. (1946b). The use of punched cards in molecular structure determinations. II. Electron diffraction calculations. J. Chem. Phys. 14, 659–664.
Shoemaker, D. P. & Sly, W. G. (1961). Computer programming strategy for crystallographic Fourier synthesis: program MIFR1. Acta Cryst. 14, 552.
Sparks, R. A., Prosen, R. J., Kruse, F. H. & Trueblood, K. N. (1956). Crystallographic calculations on the highspeed digital computer SWAC. Acta Cryst. 9, 350–358.
Suryan, G. (1957). An analogue computer for double Fourier series summation for Xray crystalstructure analysis. Acta Cryst. 10, 82–84.
Ten Eyck, L. F. (1973). Crystallographic fast Fourier transforms. Acta Cryst. A29, 183–191.