Historical introduction

Bricogne, G.

doi:10.1107/97809553602060000551

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

pdf | chapter contents | chapter index | related articles

International Tables for Crystallography (2006). Vol. B. ch. 1.3, pp. 71-72 | 1 | 2 |

Section 1.3.4.3.1. Historical introduction

G. Bricogne^a

^a MRC Laboratory of Molecular Biology, Hills Road, Cambridge CB2 2QH, 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 $[N \times N]$ transform grows with N as $[2N^{3}]$ rather than $[N^{4}]$ . Generalization to 3D is immediate, reducing computation size from $[N^{6}]$ to $[3N^{4}]$ for an $[N \times N \times N]$ 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 $[A \cos \left({2\pi hm \over 60}\right)\;\; (A = 1, 2, \ldots, 99\hbox{; } h = 1, 2, \ldots, 99)]$ and a set of `sine strips' tabulating the functions $[B \sin \left({2\pi hm \over 60}\right) \;\;(B = 1, 2, \ldots, 99\hbox{; } h = 1, 2, \ldots, 99)]$ for the 16 arguments $[m = 0, 1, \ldots, 15]$ . 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 $[Y(m) = \sum\limits_{j = 1}^{n} \left[A_{j} \cos \left({2\pi h_{j}m \over 60}\right) + B_{j} \sin \left({2\pi h_{j}m \over 60}\right)\right]]$ is then performed by selecting the n cosine strips labelled $[(A_{j}, h_{j})]$ and the n sine strips labelled $[(B_{j}, h_{j})]$ , 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 non-primitive 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 $[P\bar{1}]$ 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 $[2^{n}]$ , 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, P2₁, P222, P2₁2₁2₁, Pmmm). This package was later augmented by a handful of new space-group-specific programs contributed by other crystallographers (P2₁2₁2, I222, P3₁21, P4₁2₁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 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.Google Scholar

Ahmed, F. R. & Cruickshank, D. W. J. (1953b). Crystallographic calculations on the Manchester University electronic digital computer (Mark II). Acta Cryst. 6, 765–769.Google Scholar

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.Google Scholar

Auslander, L., Johnson, R. W. & Vulis, M. (1988). Evaluating finite Fourier transforms that respect group symmetries. Acta Cryst. A44, 467–478.Google Scholar

Auslander, L. & Shenefelt, M. (1987). Fourier transforms that respect crystallographic symmetries. IBM J. Res. Dev. 31, 213–223.Google Scholar

Bantz, D. & Zwick, M. (1974). The use of symmetry with the fast Fourier algorithm. Acta Cryst. A30, 257–260.Google Scholar

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.Google Scholar

Beevers, C. A. (1952). Fourier strips at a 3° interval. Acta Cryst. 5, 670–673.Google Scholar

Beevers, C. A. & Lipson, H. (1934). A rapid method for the summation of a two-dimensional Fourier series. Philos. Mag. 17, 855–859.Google Scholar

Beevers, C. A. & Lipson, H. (1936). A numerical method for two-dimensional Fourier synthesis. Nature (London), 137, 825–826.Google Scholar

Bennett, J. M. & Kendrew, J. C. (1952). The computation of Fourier syntheses with a digital electronic calculating machine. Acta Cryst. 5, 109–116.Google Scholar

Bondot, P. (1971). Application de la transformée de Fourier performante aux calculs cristallographiques. Acta Cryst. A27, 492–494.Google Scholar

Booth, A. D. (1948b). Fourier technique in X-ray organic structure analysis. Cambridge University Press.Google Scholar

Bragg, W. L. (1929). Determination of parameters in crystal structures by means of Fourier series. Proc. R. Soc. London Ser. A, 123, 537–559.Google Scholar

Cochran, W. (1948a). A critical examination of the Beevers–Lipson method of Fourier series summation. Acta Cryst. 1, 54–56.Google Scholar

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.Google Scholar

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.Google Scholar

Cox, E. G. & Jeffrey, G. A. (1949). The use of Hollerith computing equipment in crystal structure analysis. Acta Cryst. 2, 341–343.Google Scholar

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.Google Scholar

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.Google Scholar

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.Google Scholar

Greenhalgh, D. M. S. & Jeffrey, G. A. (1950). A new punched card method of Fourier synthesis. Acta Cryst. 3, 311–312.Google Scholar

Grems, M. D. & Kasper, J. S. (1949). An improved punched-card method for crystal structure-factor calculations. Acta Cryst. 2, 347–351.Google Scholar

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.Google Scholar

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.Google Scholar

Immirzi, A. (1976). Fast Fourier transform in crystallography. In Crystallographic computing techniques, edited by F. R. Ahmed, pp. 399–412. Copenhagen: Munksgaard.Google Scholar

Kitz, N. & Marchington, B. (1953). A method of Fourier synthesis using a standard Hollerith senior rolling total tabulator. Acta Cryst. 6, 325–326.Google Scholar

Lipson, H. & Beevers, C. A. (1936). An improved numerical method of two-dimensional Fourier synthesis for crystals. Proc. Phys. Soc. London, 48, 772–780.Google Scholar

Lipson, H. & Cochran, W. (1968). The determination of crystal structures. Revised and enlarged edition. London: G. Bell & Sons.Google Scholar

Lipson, H. & Taylor, C. A. (1951). Optical methods in X-ray analysis. II. Fourier transforms and crystal-structure determination. Acta Cryst. 4, 458–462.Google Scholar

Lipson, H. & Taylor, C. A. (1958). Fourier transforms and X-ray diffraction. London: Bell.Google Scholar

Lonsdale, K. (1936). Simplified structure factor and electron density formulae for the 230 space groups of mathematical crystallography. London: Bell.Google Scholar

Mayer, S. W. & Trueblood, K. N. (1953). Three-dimensional Fourier summations on a high-speed digital computer. Acta Cryst. 6, 427.Google Scholar

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.Google Scholar

Pepinsky, R. (1947). An electronic computer for X-ray crystal structure analyses. J. Appl. Phys. 18, 601–604.Google Scholar

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.Google Scholar

Pepinsky, R. & Sayre, D. (1948). Quantitative electron-density contour delineation in the electronic Fourier synthesizer for crystal structure analysis. Nature (London), 162, 22–23.Google Scholar

Robertson, J. M. (1932). A simple harmonic continuous calculating machine. Philos. Mag. 13, 413–419.Google Scholar

Robertson, J. M. (1936a). Numerical and mechanical methods in double Fourier synthesis. Philos. Mag. 21, 176–187.Google Scholar

Robertson, J. M. (1936b). Calculation of structure factors and summation of Fourier series in crystal analysis: non-centrosymmetrical projections. Nature (London), 138, 683–684.Google Scholar

Robertson, J. M. (1954). A fast digital computer for Fourier operations. Acta Cryst. 7, 817–822.Google Scholar

Robertson, J. M. (1955). Some properties of Fourier strips with applications to the digital computer. Acta Cryst. 8, 286–288.Google Scholar

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.Google Scholar

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.Google Scholar

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.Google Scholar

Shoemaker, D. P. & Sly, W. G. (1961). Computer programming strategy for crystallographic Fourier synthesis: program MIFR1. Acta Cryst. 14, 552.Google Scholar

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.Google Scholar

Suryan, G. (1957). An analogue computer for double Fourier series summation for X-ray crystal-structure analysis. Acta Cryst. 10, 82–84.Google Scholar

Ten Eyck, L. F. (1973). Crystallographic fast Fourier transforms. Acta Cryst. A29, 183–191.Google Scholar

International Tables for Crystallography (2006). Vol. B. ch. 1.3, pp. 71-72