Agarwal's FFT implementation of the Fourier method

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. 90-91 | 1 | 2 |

Section 1.3.4.4.7.6. Agarwal's FFT implementation of the Fourier method

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.4.7.6. Agarwal's FFT implementation of the Fourier method

| top | pdf |

Agarwal (1978) rederived and completed Cruickshank's results at a time when the availability of the FFT algorithm made the Fourier method of calculating the coefficients of the normal equations much more economical than the standard method, especially for macromolecules.

As obtained by Cruickshank, the modified Fourier method required a full 3D Fourier synthesis

– for each type of parameter, since this determines [via the polynomial $[P_{p} ({\bf h})]$ ] the type of differential synthesis to be computed;
– for each type of atom $[j \in J]$ , since the coefficients of the differential synthesis must be multiplied by $[g_{j}({\bf h})]$ .

Agarwal disposed of the latter dependence by pointing out that the multiplication involved is equivalent to a real-space convolution between the differential synthesis and $[\sigma\llap{$-$}_{j} ({\bf x})]$ , the standard electron density $[\rho\llap{$-\!$}_{j}]$ for atom type j (Section 1.3.4.2.1.2) smeared by the isotropic thermal agitation of that atom. Since $[\sigma\llap{$-$}_{j}]$ is localized, this convolution involves only a small number of grid points. The requirement of a distinct differential synthesis for each parameter type, however, continued to hold, and created some difficulties at the FFT level because the symmetries of differential syntheses are more complex than ordinary space-group symmetries. Jack & Levitt (1978) sought to avoid the calculation of difference syntheses by using instead finite differences calculated from ordinary Fourier or difference Fourier maps.

In spite of its complication, this return to the Fourier implementation of the least-squares method led to spectacular increases in speed (Isaacs & Agarwal, 1978; Agarwal, 1980; Baker & Dodson, 1980) and quickly gained general acceptance (Dodson, 1981; Isaacs, 1982a,b, 1984).

References

Agarwal, R. C. (1978). A new least-squares refinement technique based on the fast Fourier transform algorithm. Acta Cryst. A34, 791–809.Google Scholar

Agarwal, R. C. (1980). The refinement of crystal structure by fast Fourier least-squares. In Computing in crystallography, edited by R. Diamond, S. Ramaseshan & K. Venkatesan, pp. 18.01–18.13. Bangalore: The Indian Academy of Science.Google Scholar

Baker, E. N. & Dodson, E. J. (1980). Crystallographic refinement of the structure of actinidin at 1.7 Å resolution by fast Fourier least-squares methods. Acta Cryst. A36, 559–572.Google Scholar

Dodson, E. J. (1981). Block diagonal least squares refinement using fast Fourier techniques. In Refinement of protein structures, compiled by P. A. Machin J. W. Campbell & M. Elder (ref. DL/SCI/R16), pp. 29–39. Warrington: SERC Daresbury Laboratory.Google Scholar

Isaacs, N. W. (1982a). The refinement of macromolecules. In Computational crystallography, edited by D. Sayre, pp. 381–397. New York: Oxford University Press.Google Scholar

Isaacs, N. W. (1982b). Refinement techniques: use of the FFT. In Computational crystallography, edited by D. Sayre, pp. 398–408. New York: Oxford University Press.Google Scholar

Isaacs, N. W. (1984). Refinement using the fast-Fourier transform least squares algorithm. In Methods and applications in crystallographic computing, edited by S. R. Hall & T. Ashida, pp. 193–205. New York: Oxford University Press.Google Scholar

Isaacs, N. W. & Agarwal, R. C. (1978). Experience with fast Fourier least squares in the refinement of the crystal structure of rhombohedral 2-zinc insulin at 1.5 Å resolution. Acta Cryst. A34, 782–791.Google Scholar

Jack, A. & Levitt, M. (1978). Refinement of large structures by simultaneous minimization of energy and R factor. Acta Cryst. A34, 931–935.Google Scholar

International Tables for Crystallography (2006). Vol. B. ch. 1.3, pp. 90-91