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

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

Section 1.3.4.3.5.1. Hermitian-symmetric or real-valued transforms

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.5.1. Hermitian-symmetric or real-valued transforms

| top | pdf |

The computation of a DFT with Hermitian-symmetric or real-valued data can be carried out at a cost of half that of an ordinary transform, essentially by multiplexing' pairs of special partial transforms into general complex transforms, and then demultiplexing' the results on the basis of their symmetry properties. The treatment given below is for general dimension n; a subset of cases for was treated by Ten Eyck (1973).

• (a) Underlying group action

Hermitian symmetry is not a geometric symmetry, but it is defined in terms of the action in reciprocal space of point group , i.e. , where e acts as I (the identity matrix) and acts as .

This group action on with will now be characterized by the calculation of the cocycle (Section 1.3.4.3.4.1) under the assumption that and are both diagonal. For this purpose it is convenient to associate to any integer vectorin the vector whose jth component is

Let , and hence . ThenhenceTherefore −e acts by

Hermitian symmetry is traditionally dealt with by factoring by 2, i.e. by assuming . If , then each is invariant under G, so that each partial vector (Section 1.3.4.3.4.1) inherits the symmetry internally, with a modulation' by . The multiplexing–demultiplexing' technique provides an efficient treatment of this singular case.

• (b) Calculation of structure factors

The computation may be summarized as follows:where is the initial decimation given by , TW is the transposition and twiddle-factor stage, and is the final unscrambling by coset reversal given by .

 (i) Decimation in time The decimated vectors are real and hence have Hermitian transforms . The values of may be grouped into pairs and the vectors corresponding to each pair may be multiplexed into a general complex vectorThe transform can then be resolved into the separate transforms and by using the Hermitian symmetry of the latter, which yields the demultiplexing formulaeThe number of partial transforms is thus reduced from to . Once this separation has been achieved, the remaining steps need only be carried out for a unique half of the values of . (ii) Decimation in frequency Since we have and mod . The vectors of decimated and scrambled results then obey the symmetry relationswhich can be used to halve the number of necessary to compute them, as follows. Having formed the vectors given bywe may group the values of into pairs and for each pair form the multiplexed vector:After calculating the transforms , the individual transforms and can be separated by using for each pair the demultiplexing formulaewhich can be solved recursively. If all pairs are chosen so that they differ only in the jth coordinate , the recursion is along and can be initiated by introducing the (real) values of and at and , accumulated e.g. while forming Z for that pair. Only points with going from 0 to need be resolved, and they contain the unique half of the Hermitian-symmetric transform F.

• (c) Calculation of electron densities

The computation may be summarized as follows:where is the decimation with coset reversal given by , TW is the transposition and twiddle-factor stage, and is the recovery in natural order given by .

 (i) Decimation in time The last transformation has a real-valued matrix, and the final result is real-valued. It follows that the vectors of intermediate results after the twiddle-factor stage are real-valued, hence lend themselves to multiplexing along the real and imaginary components of half as many general complex vectors. Let the initial vectors be multiplexed into vectors[one for each pair ], each of which yields by F(M) a vectorThe real-valuedness of the may be used to recover the separate result vectors for and . For this purpose, introduce the abbreviated notationThen we may writeor, equivalently, for each ,Therefore and may be retrieved from Z by the `demultiplexing' formula:which is valid at all points where , i.e. whereDemultiplexing fails whenIf the pairs are chosen so that their members differ only in one coordinate (the jth, say), then the exceptional points are at and the missing transform values are easily obtained e.g. by accumulation while forming . The final stage of the calculation is then (ii) Decimation in frequency The last transformation F(M) gives the real-valued results , therefore the vectors after the twiddle-factor stage each have Hermitian symmetry. A first consequence is that the intermediate vectors need only be computed for the unique half of the values of , the other half being related by the Hermitian symmetry of . A second consequence is that the vectors may be condensed into general complex vectors[one for each pair ] to which a general complex F(M) may be applied to yieldwith and real-valued. The final results can therefore be retrieved by the particularly simple demultiplexing formulae:

References

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