Fourier transforms in crystallography: theory, algorithms and applications

Bricogne, G.

doi:10.1107/97809553602060000551

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

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

1.3. Fourier transforms in crystallography: theory, algorithms and applications (pp. 25-98) | html | pdf | chapter contents |
G. Bricogne
- 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 (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 (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 (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 |

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

Contents