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

International Tables for Crystallography (2010). Vol. B, ch. 1.3, pp. 76-77   | 1 | 2 |

Section 1.3.4.3.1. Historical 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.4.3.1. Historical introduction

| top | pdf |

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 functionsand a set of sine strips' tabulating the functionsfor 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 formis 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 two-digit 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 three-digit 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 special-purpose mechanical, electro-mechanical, 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 X-RAC built by Pepinsky, capable of real-time 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 punched-card machines were programmed to carry out Fourier summations or structure-factor 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 Fourier-synthesis 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 signal-processing 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 multi-radix 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 re-analysing them into structure factors in some simple space groups (P1, P1, P2, P2/m, P21, P222, P212121, Pmmm). This package was later augmented by a handful of new space-group-specific programs contributed by other crystallographers (P21212, I222, P3121, P41212). 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 high-symmetry 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 three-dimensional 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 built-in 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 3-dimensional 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 two-dimensional Fourier series. Philos. Mag. 17, 855–859.
Beevers, C. A. & Lipson, H. (1936). A numerical method for two-dimensional 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 X-ray 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 punched-card 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 three-dimensional differential Fourier syntheses in X-ray 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 X-ray 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: 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 punched-card method for crystal structure-factor 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 X-ray crystal-structure 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 two-dimensional 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 X-ray analysis. II. Fourier transforms and crystal-structure determination. Acta Cryst. 4, 458–462.
Lipson, H. & Taylor, C. A. (1958). Fourier Transforms and X-ray 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). Three-dimensional Fourier summations on a high-speed digital computer. Acta Cryst. 6, 427.
Niggli, A. (1961). Small-scale computers in X-ray 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 X-ray crystal structure analyses. J. Appl. Phys. 18, 601–604.
Pepinsky, R., van den Hende, J. & Vand, V. (1961). X-RAC 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 electron-density 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: non-centrosymmetrical 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 high-speed digital computer SWAC. Acta Cryst. 9, 350–358.
Suryan, G. (1957). An analogue computer for double Fourier series summation for X-ray crystal-structure analysis. Acta Cryst. 10, 82–84.
Ten Eyck, L. F. (1973). Crystallographic fast Fourier transforms. Acta Cryst. A29, 183–191.