International Tables for Crystallography (2006). Vol. B, ch. 1.3, pp. 25-98   | 1 | 2 |
doi: 10.1107/97809553602060000551

Chapter 1.3. Fourier transforms in crystallography: theory, algorithms and applications

Contents

  • 1.3. Fourier transforms in crystallography: theory, algorithms and applications  (pp. 25-98) | html | pdf | chapter contents |
    • 1.3.1. General introduction  (p. 25) | html | pdf |
    • 1.3.2. The mathematical theory of the Fourier transformation  (pp. 25-49) | html | pdf |
      • 1.3.2.1. Introduction  (pp. 25-26) | html | pdf |
      • 1.3.2.2. Preliminary notions and notation  (pp. 26-28) | html | pdf |
        • 1.3.2.2.1. Metric and topological notions in [{\bb R}^{n}]  (p. 26) | html | pdf |
        • 1.3.2.2.2. Functions over [{\bb R}^{n}]  (pp. 26-27) | html | pdf |
        • 1.3.2.2.3. Multi-index notation  (p. 27) | html | pdf |
        • 1.3.2.2.4. Integration, [L^{p}] spaces  (p. 27) | html | pdf |
        • 1.3.2.2.5. Tensor products. Fubini's theorem  (pp. 27-28) | html | pdf |
        • 1.3.2.2.6. Topology in function spaces  (p. 28) | html | pdf |
          • 1.3.2.2.6.1. General topology  (p. 28) | html | pdf |
          • 1.3.2.2.6.2. Topological vector spaces  (p. 28) | html | pdf |
      • 1.3.2.3. Elements of the theory of distributions  (pp. 28-34) | html | pdf |
        • 1.3.2.3.1. Origins  (p. 29) | html | pdf |
        • 1.3.2.3.2. Rationale  (p. 29) | html | pdf |
        • 1.3.2.3.3. Test-function spaces  (pp. 29-30) | html | pdf |
          • 1.3.2.3.3.1. Topology on [{\scr E}(\Omega)]  (pp. 29-30) | html | pdf |
          • 1.3.2.3.3.2. Topology on [{\scr D}_{k} (\Omega)]  (p. 30) | html | pdf |
          • 1.3.2.3.3.3. Topology on [{\scr D}(\Omega)]  (p. 30) | html | pdf |
          • 1.3.2.3.3.4. Topologies on [{\scr E}^{(m)}, {\scr D}_{k}^{(m)},{\scr D}^{(m)}]  (p. 30) | html | pdf |
        • 1.3.2.3.4. Definition of distributions  (p. 30) | html | pdf |
        • 1.3.2.3.5. First examples of distributions  (p. 30) | html | pdf |
        • 1.3.2.3.6. Distributions associated to locally integrable functions  (pp. 30-31) | html | pdf |
        • 1.3.2.3.7. Support of a distribution  (p. 31) | html | pdf |
        • 1.3.2.3.8. Convergence of distributions  (p. 31) | html | pdf |
        • 1.3.2.3.9. Operations on distributions  (pp. 31-34) | html | pdf |
          • 1.3.2.3.9.1. Differentiation  (pp. 31-32) | html | pdf |
          • 1.3.2.3.9.2. Integration of distributions in dimension 1  (p. 32) | html | pdf |
          • 1.3.2.3.9.3. Multiplication of distributions by functions  (p. 32) | html | pdf |
          • 1.3.2.3.9.4. Division of distributions by functions  (p. 33) | html | pdf |
          • 1.3.2.3.9.5. Transformation of coordinates  (p. 33) | html | pdf |
          • 1.3.2.3.9.6. Tensor product of distributions  (p. 33) | html | pdf |
          • 1.3.2.3.9.7. Convolution of distributions  (pp. 33-34) | html | pdf |
      • 1.3.2.4. Fourier transforms of functions  (pp. 34-38) | html | pdf |
        • 1.3.2.4.1. Introduction  (p. 34) | html | pdf |
        • 1.3.2.4.2. Fourier transforms in [L^{1}]  (pp. 35-37) | html | pdf |
          • 1.3.2.4.2.1. Linearity  (p. 35) | html | pdf |
          • 1.3.2.4.2.2. Effect of affine coordinate transformations  (p. 35) | html | pdf |
          • 1.3.2.4.2.3. Conjugate symmetry  (p. 35) | html | pdf |
          • 1.3.2.4.2.4. Tensor product property  (p. 35) | html | pdf |
          • 1.3.2.4.2.5. Convolution property  (p. 35) | html | pdf |
          • 1.3.2.4.2.6. Reciprocity property  (p. 35) | html | pdf |
          • 1.3.2.4.2.7. Riemann–Lebesgue lemma  (p. 35) | html | pdf |
          • 1.3.2.4.2.8. Differentiation  (pp. 35-36) | html | pdf |
          • 1.3.2.4.2.9. Decrease at infinity  (p. 36) | html | pdf |
          • 1.3.2.4.2.10. The Paley–Wiener theorem  (p. 36) | html | pdf |
        • 1.3.2.4.3. Fourier transforms in [L^{2}]  (pp. 36-37) | html | pdf |
          • 1.3.2.4.3.1. Invariance of [L^{2}]  (p. 36) | html | pdf |
          • 1.3.2.4.3.2. Reciprocity  (p. 36) | html | pdf |
          • 1.3.2.4.3.3. Isometry  (p. 36) | html | pdf |
          • 1.3.2.4.3.4. Eigenspace decomposition of [L^{2}]  (p. 36) | html | pdf |
          • 1.3.2.4.3.5. The convolution theorem and the isometry property  (pp. 36-37) | html | pdf |
        • 1.3.2.4.4. Fourier transforms in [{\scr S}]  (pp. 37-38) | html | pdf |
          • 1.3.2.4.4.1. Definition and properties of [{\scr S}]  (p. 37) | html | pdf |
          • 1.3.2.4.4.2. Gaussian functions and Hermite functions  (pp. 37-38) | html | pdf |
          • 1.3.2.4.4.3. Heisenberg's inequality, Hardy's theorem  (p. 38) | html | pdf |
          • 1.3.2.4.4.4. Symmetry property  (p. 38) | html | pdf |
        • 1.3.2.4.5. Various writings of Fourier transforms  (p. 38) | html | pdf |
        • 1.3.2.4.6. Tables of Fourier transforms  (p. 38) | html | pdf |
      • 1.3.2.5. Fourier transforms of tempered distributions  (pp. 38-40) | html | pdf |
        • 1.3.2.5.1. Introduction  (pp. 38-39) | html | pdf |
        • 1.3.2.5.2. [{\scr S}] as a test-function space  (p. 39) | html | pdf |
        • 1.3.2.5.3. Definition and examples of tempered distributions  (p. 39) | html | pdf |
        • 1.3.2.5.4. Fourier transforms of tempered distributions  (p. 39) | html | pdf |
        • 1.3.2.5.5. Transposition of basic properties  (p. 39) | html | pdf |
        • 1.3.2.5.6. Transforms of δ-functions  (pp. 39-40) | html | pdf |
        • 1.3.2.5.7. Reciprocity theorem  (p. 40) | html | pdf |
        • 1.3.2.5.8. Multiplication and convolution  (p. 40) | html | pdf |
        • 1.3.2.5.9. [L^{2}] aspects, Sobolev spaces  (p. 40) | html | pdf |
      • 1.3.2.6. Periodic distributions and Fourier series  (pp. 40-45) | html | pdf |
        • 1.3.2.6.1. Terminology  (pp. 40-41) | html | pdf |
        • 1.3.2.6.2. [{\bb Z}^{n}]-periodic distributions in [{\bb R}^{n}]  (p. 41) | html | pdf |
        • 1.3.2.6.3. Identification with distributions over [{\bb R}^{n}/{\bb Z}^{n}]  (p. 41) | html | pdf |
        • 1.3.2.6.4. Fourier transforms of periodic distributions  (pp. 41-42) | html | pdf |
        • 1.3.2.6.5. The case of non-standard period lattices  (p. 42) | html | pdf |
        • 1.3.2.6.6. Duality between periodization and sampling  (p. 42) | html | pdf |
        • 1.3.2.6.7. The Poisson summation formula  (pp. 42-43) | html | pdf |
        • 1.3.2.6.8. Convolution of Fourier series  (p. 43) | html | pdf |
        • 1.3.2.6.9. Toeplitz forms, Szegö's theorem  (pp. 43-44) | html | pdf |
          • 1.3.2.6.9.1. Toeplitz forms  (p. 43) | html | pdf |
          • 1.3.2.6.9.2. The Toeplitz–Carathéodory–Herglotz theorem  (p. 43) | html | pdf |
          • 1.3.2.6.9.3. Asymptotic distribution of eigenvalues of Toeplitz forms  (pp. 43-44) | html | pdf |
          • 1.3.2.6.9.4. Consequences of Szegö's theorem  (p. 44) | html | pdf |
        • 1.3.2.6.10. Convergence of Fourier series  (pp. 44-45) | html | pdf |
          • 1.3.2.6.10.1. Classical [L^{1}] theory  (pp. 44-45) | html | pdf |
          • 1.3.2.6.10.2. Classical [L^{2}] theory  (p. 45) | html | pdf |
          • 1.3.2.6.10.3. The viewpoint of distribution theory  (p. 45) | html | pdf |
      • 1.3.2.7. The discrete Fourier transformation  (pp. 45-49) | html | pdf |
        • 1.3.2.7.1. Shannon's sampling theorem and interpolation formula  (pp. 45-46) | html | pdf |
        • 1.3.2.7.2. Duality between subdivision and decimation of period lattices  (pp. 46-47) | html | pdf |
          • 1.3.2.7.2.1. Geometric description of sublattices  (p. 46) | html | pdf |
          • 1.3.2.7.2.2. Sublattice relations for reciprocal lattices  (p. 46) | html | pdf |
          • 1.3.2.7.2.3. Relation between lattice distributions  (pp. 46-47) | html | pdf |
          • 1.3.2.7.2.4. Relation between Fourier transforms  (p. 47) | html | pdf |
          • 1.3.2.7.2.5. Sublattice relations in terms of periodic distributions  (p. 47) | html | pdf |
        • 1.3.2.7.3. Discretization of the Fourier transformation  (pp. 47-48) | html | pdf |
        • 1.3.2.7.4. Matrix representation of the discrete Fourier transform (DFT)  (p. 49) | html | pdf |
        • 1.3.2.7.5. Properties of the discrete Fourier transform  (p. 49) | html | pdf |
    • 1.3.3. Numerical computation of the discrete Fourier transform  (pp. 49-58) | html | pdf |
      • 1.3.3.1. Introduction  (pp. 49-50) | html | pdf |
      • 1.3.3.2. One-dimensional algorithms  (pp. 50-55) | html | pdf |
        • 1.3.3.2.1. The Cooley–Tukey algorithm  (pp. 50-51) | html | pdf |
        • 1.3.3.2.2. The Good (or prime factor) algorithm  (pp. 51-52) | html | pdf |
          • 1.3.3.2.2.1. Ring structure on [{\bb Z}/N{\bb Z}]  (p. 51) | html | pdf |
          • 1.3.3.2.2.2. The Chinese remainder theorem  (pp. 51-52) | html | pdf |
          • 1.3.3.2.2.3. The prime factor algorithm  (p. 52) | html | pdf |
        • 1.3.3.2.3. The Rader algorithm  (pp. 53-54) | html | pdf |
          • 1.3.3.2.3.1. N an odd prime  (p. 53) | html | pdf |
          • 1.3.3.2.3.2. N a power of an odd prime  (p. 53) | html | pdf |
          • 1.3.3.2.3.3. N a power of 2  (pp. 53-54) | html | pdf |
        • 1.3.3.2.4. The Winograd algorithms  (pp. 54-55) | html | pdf |
      • 1.3.3.3. Multidimensional algorithms  (pp. 55-58) | html | pdf |
        • 1.3.3.3.1. The method of successive one-dimensional transforms  (p. 55) | html | pdf |
        • 1.3.3.3.2. Multidimensional factorization  (pp. 55-57) | html | pdf |
          • 1.3.3.3.2.1. Multidimensional Cooley–Tukey factorization  (pp. 55-56) | html | pdf |
          • 1.3.3.3.2.2. Multidimensional prime factor algorithm  (p. 56) | html | pdf |
          • 1.3.3.3.2.3. Nesting of Winograd small FFTs  (pp. 56-57) | html | pdf |
          • 1.3.3.3.2.4. The Nussbaumer–Quandalle algorithm  (p. 57) | html | pdf |
        • 1.3.3.3.3. Global algorithm design  (pp. 57-58) | html | pdf |
          • 1.3.3.3.3.1. From local pieces to global algorithms  (pp. 57-58) | html | pdf |
          • 1.3.3.3.3.2. Computer architecture considerations  (p. 58) | html | pdf |
          • 1.3.3.3.3.3. The Johnson–Burrus family of algorithms  (p. 58) | html | pdf |
    • 1.3.4. Crystallographic applications of Fourier transforms  (pp. 58-98) | html | pdf |
      • 1.3.4.1. Introduction  (pp. 58-59) | html | pdf |
      • 1.3.4.2. Crystallographic Fourier transform theory  (pp. 59-71) | html | pdf |
        • 1.3.4.2.1. Crystal periodicity  (pp. 59-64) | html | pdf |
          • 1.3.4.2.1.1. Period lattice, reciprocal lattice and structure factors  (pp. 59-60) | html | pdf |
          • 1.3.4.2.1.2. Structure factors in terms of form factors  (p. 60) | html | pdf |
          • 1.3.4.2.1.3. Fourier series for the electron density and its summation  (p. 60) | html | pdf |
          • 1.3.4.2.1.4. Friedel's law, anomalous scatterers  (p. 60) | html | pdf |
          • 1.3.4.2.1.5. Parseval's identity and other [L^{2}] theorems  (p. 61) | html | pdf |
          • 1.3.4.2.1.6. Convolution, correlation and Patterson function  (p. 61) | html | pdf |
          • 1.3.4.2.1.7. Sampling theorems, continuous transforms, interpolation  (pp. 61-62) | html | pdf |
          • 1.3.4.2.1.8. Sections and projections  (pp. 62-63) | html | pdf |
          • 1.3.4.2.1.9. Differential syntheses  (p. 63) | html | pdf |
          • 1.3.4.2.1.10. Toeplitz forms, determinantal inequalities and Szegö's theorem  (pp. 63-64) | html | pdf |
        • 1.3.4.2.2. Crystal symmetry  (pp. 64-71) | html | pdf |
          • 1.3.4.2.2.1. Crystallographic groups  (p. 64) | html | pdf |
          • 1.3.4.2.2.2. Groups and group actions  (pp. 64-66) | html | pdf |
          • 1.3.4.2.2.3. Classification of crystallographic groups  (pp. 66-67) | html | pdf |
          • 1.3.4.2.2.4. Crystallographic group action in real space  (pp. 67-68) | html | pdf |
          • 1.3.4.2.2.5. Crystallographic group action in reciprocal space  (p. 68) | html | pdf |
          • 1.3.4.2.2.6. Structure-factor calculation  (pp. 68-69) | html | pdf |
          • 1.3.4.2.2.7. Electron-density calculations  (p. 69) | html | pdf |
          • 1.3.4.2.2.8. Parseval's theorem with crystallographic symmetry  (p. 69) | html | pdf |
          • 1.3.4.2.2.9. Convolution theorems with crystallographic symmetry  (p. 70) | html | pdf |
          • 1.3.4.2.2.10. Correlation and Patterson functions  (pp. 70-71) | html | pdf |
      • 1.3.4.3. Crystallographic discrete Fourier transform algorithms  (pp. 71-84) | html | pdf |
        • 1.3.4.3.1. Historical introduction  (pp. 71-72) | html | pdf |
        • 1.3.4.3.2. Defining relations and symmetry considerations  (pp. 72-73) | html | pdf |
        • 1.3.4.3.3. Interaction between symmetry and decomposition  (p. 73) | html | pdf |
        • 1.3.4.3.4. Interaction between symmetry and factorization  (pp. 73-79) | html | pdf |
          • 1.3.4.3.4.1. Multidimensional Cooley–Tukey factorization  (pp. 74-76) | html | pdf |
          • 1.3.4.3.4.2. Multidimensional Good factorization  (p. 76) | html | pdf |
          • 1.3.4.3.4.3. Crystallographic extension of the Rader/Winograd factorization  (pp. 76-79) | html | pdf |
        • 1.3.4.3.5. Treatment of conjugate and parity-related symmetry properties  (pp. 79-82) | html | pdf |
          • 1.3.4.3.5.1. Hermitian-symmetric or real-valued transforms  (pp. 79-80) | html | pdf |
          • 1.3.4.3.5.2. Hermitian-antisymmetric or pure imaginary transforms  (p. 80) | html | pdf |
          • 1.3.4.3.5.3. Complex symmetric and antisymmetric transforms  (pp. 80-81) | html | pdf |
          • 1.3.4.3.5.4. Real symmetric transforms  (p. 81) | html | pdf |
          • 1.3.4.3.5.5. Real antisymmetric transforms  (p. 82) | html | pdf |
          • 1.3.4.3.5.6. Generalized multiplexing  (p. 82) | html | pdf |
        • 1.3.4.3.6. Global crystallographic algorithms  (pp. 82-84) | html | pdf |
          • 1.3.4.3.6.1. Triclinic groups  (p. 82) | html | pdf |
          • 1.3.4.3.6.2. Monoclinic groups  (p. 82) | html | pdf |
          • 1.3.4.3.6.3. Orthorhombic groups  (pp. 82-83) | html | pdf |
          • 1.3.4.3.6.4. Trigonal, tetragonal and hexagonal groups  (p. 83) | html | pdf |
          • 1.3.4.3.6.5. Cubic groups  (p. 83) | html | pdf |
          • 1.3.4.3.6.6. Treatment of centred lattices  (p. 83) | html | pdf |
          • 1.3.4.3.6.7. Programming considerations  (pp. 83-84) | html | pdf |
      • 1.3.4.4. Basic crystallographic computations  (pp. 84-93) | html | pdf |
        • 1.3.4.4.1. Introduction  (p. 84) | html | pdf |
        • 1.3.4.4.2. Fourier synthesis of electron-density maps  (p. 84) | html | pdf |
        • 1.3.4.4.3. Fourier analysis of modified electron-density maps  (pp. 84-86) | html | pdf |
          • 1.3.4.4.3.1. Squaring  (p. 84) | html | pdf |
          • 1.3.4.4.3.2. Other non-linear operations  (p. 84) | html | pdf |
          • 1.3.4.4.3.3. Solvent flattening  (pp. 84-85) | html | pdf |
          • 1.3.4.4.3.4. Molecular averaging by noncrystallographic symmetries  (pp. 85-86) | html | pdf |
          • 1.3.4.4.3.5. Molecular-envelope transforms via Green's theorem  (p. 86) | html | pdf |
        • 1.3.4.4.4. Structure factors from model atomic parameters  (p. 86) | html | pdf |
        • 1.3.4.4.5. Structure factors via model electron-density maps  (pp. 86-87) | html | pdf |
        • 1.3.4.4.6. Derivatives for variational phasing techniques  (pp. 87-88) | html | pdf |
        • 1.3.4.4.7. Derivatives for model refinement  (pp. 88-92) | html | pdf |
          • 1.3.4.4.7.1. The method of least squares  (p. 88) | html | pdf |
          • 1.3.4.4.7.2. Booth's differential Fourier syntheses  (pp. 88-89) | html | pdf |
          • 1.3.4.4.7.3. Booth's method of steepest descents  (p. 89) | html | pdf |
          • 1.3.4.4.7.4. Cochran's Fourier method  (pp. 89-90) | html | pdf |
          • 1.3.4.4.7.5. Cruickshank's modified Fourier method  (p. 90) | html | pdf |
          • 1.3.4.4.7.6. Agarwal's FFT implementation of the Fourier method  (pp. 90-91) | html | pdf |
          • 1.3.4.4.7.7. Lifchitz's reformulation  (p. 91) | html | pdf |
          • 1.3.4.4.7.8. A simplified derivation  (p. 91) | html | pdf |
          • 1.3.4.4.7.9. Discussion of macromolecular refinement techniques  (p. 92) | html | pdf |
          • 1.3.4.4.7.10. Sampling considerations  (p. 92) | html | pdf |
        • 1.3.4.4.8. Miscellaneous correlation functions  (p. 92) | html | pdf |
      • 1.3.4.5. Related applications  (pp. 93-98) | html | pdf |
        • 1.3.4.5.1. Helical diffraction  (pp. 93-94) | html | pdf |
          • 1.3.4.5.1.1. Circular harmonic expansions in polar coordinates  (p. 93) | html | pdf |
          • 1.3.4.5.1.2. The Fourier transform in polar coordinates  (p. 93) | html | pdf |
          • 1.3.4.5.1.3. The transform of an axially periodic fibre  (p. 93) | html | pdf |
          • 1.3.4.5.1.4. Helical symmetry and associated selection rules  (pp. 93-94) | html | pdf |
        • 1.3.4.5.2. Application to probability theory and direct methods  (pp. 94-98) | html | pdf |
          • 1.3.4.5.2.1. Analytical methods of probability theory  (pp. 94-96) | html | pdf |
          • 1.3.4.5.2.2. The statistical theory of phase determination  (pp. 96-98) | html | pdf |
    • References | html | pdf |
    • Figures
      • Fig. 1.3.3.1. A few global algorithms for computing a 400-point DFT  (p. 58) | html | pdf |