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 [n = 1] was treated by Ten Eyck (1973)[link].

  • (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 [G = \bar{1}], i.e. [G = \{e, -e\}], where e acts as I (the [n \times n] identity matrix) and [-e] acts as [-{\bf I}].

    This group action on [{\bb Z}^{n} / {\bf N}{\bb Z}^{n}] with [{\bf N} = {\bf N}_{1} {\bf N}_{2}] will now be characterized by the calculation of the cocycle [{\boldeta}_{1}] (Section 1.3.4.3.4.1[link]) under the assumption that [{\bf N}_{1}] and [{\bf N}_{2}] are both diagonal. For this purpose it is convenient to associate to any integer vector[{\bf v} = \pmatrix{v_{1}\cr \vdots\cr v_{n}\cr}]in [{\bb Z}^{n}] the vector [\boldzeta (\bf v)] whose jth component is[\cases{0 \hbox{ if } &$v_{j} = 0$\cr 1 \hbox{ if } &$v_{j} \neq 0$.\cr}]

    Let [{\bf m} = {\bf m}_{1} + {\bf N}_{1} {\bf m}_{2}], and hence [{\bf h} = {\bf h}_{2} + {\bf N}_{2} {\bf h}_{1}]. Then[\eqalign{&-{\bf h}_{2} \hbox{ mod } {\bf N} {\bb Z}^{n} = {\bf N} {\boldzeta} ({\bf h}_{2}) - {\bf h}_{2},\cr &-{\bf h}_{2} \hbox{ mod } {\bf N}_{2} {\bb Z}^{n} = {\bf N}_{2} {\boldzeta} ({\bf h}_{2}) - {\bf h}_{2},}]hence[\eqalign{{\boldeta}_{1} (-{e, {\bf h}}_{2}) &= {\bf N}_{2}^{-1} \{[{\bf N} {\boldzeta} ({\bf h}_{2}) - {\bf h}_{2}] - [{\bf N}_{2} {\boldzeta} ({\bf h}_{2}) - {\bf h}_{2}]\} \hbox{ mod } {\bf N}_{1} {\bb Z}^{n}\cr &= -{\boldzeta} ({\bf h}_{2}) \hbox{ mod } {\bf N}_{1} {\bb Z}^{n}.}]Therefore −e acts by[({\bf h}_{2}, {\bf h}_{1}) \,\longmapsto\, [{\bf N}_{2} {\boldzeta} ({\bf h}_{2}) - {\bf h}_{2}, {\bf N}_{1} {\boldzeta} ({\bf h}_{1}) - {\bf h}_{1} - {\boldzeta} ({\bf h}_{2})].]

    Hermitian symmetry is traditionally dealt with by factoring by 2, i.e. by assuming [{\bf N} = 2{\bf M}]. If [{\bf N}_{2} = 2{\bf I}], then each [{\bf h}_{2}] is invariant under G, so that each partial vector [{\bf Z}_{{\bf h}_{2}}^{*}] (Section 1.3.4.3.4.1[link]) inherits the symmetry internally, with a `modulation' by [{\boldeta}_{1} (g, {\bf h}_{2})]. The `multiplexing–demultiplexing' technique provides an efficient treatment of this singular case.

  • (b) Calculation of structure factors

    The computation may be summarized as follows:[\rho\llap{$-\!$} {\buildrel{{\bf dec}({\bf N}_{1})} \over {\,\longmapsto\,}} {\bf Y} {\buildrel {\bar{F} ({\bf N}_{2})} \over {\,\longmapsto\,}} {\bf Y}^{*} {\buildrel {\scriptstyle{\rm TW}} \over {\,\longmapsto\,}} {\bf Z} {\buildrel{\bar{F} ({\bf N}_{1})} \over {\,\longmapsto\,}} {\bf Z}^{*} {\buildrel{{\bf rev}({\bf N}_{2})} \over {\,\longmapsto\,}} {\bf F}]where [{\bf dec}({\bf N}_{1})] is the initial decimation given by [Y_{{\bf m}_{1}} ({\bf m}_{2}) = \rho\llap{$-\!$} ({\bf m}_{1} + {\bf N}_{1} {\bf m}_{2})], TW is the transposition and twiddle-factor stage, and [{\bf rev}({\bf N}_{2})] is the final unscrambling by coset reversal given by [F ({\bf h}_{2} + {\bf N}_{2} {\bf h}_{1}) = {\bf Z}_{{\bf h}_{2}}^{*} ({\bf h}_{1})].

    • (i) Decimation in time [({\bf N}_{1} = 2{\bf I},{\bf N}_{2} = {\bf M})]

      The decimated vectors [{\bf Y}_{{\bf m}_{1}}] are real and hence have Hermitian transforms [{\bf Y}_{{\bf m}_{1}}^{*}]. The [2^{n}] values of [{\bf m}_{1}] may be grouped into [2^{n - 1}] pairs [({\bf m}'_{1}, {\bf m}''_{1})] and the vectors corresponding to each pair may be multiplexed into a general complex vector[{\bf Y} = {\bf Y}_{{\bf m}'_{1}} + i {\bf Y}_{{\bf m}''_{1}}.]The transform [{\bf Y}^{*} = \bar{F} ({\bf M}) [{\bf Y}]] can then be resolved into the separate transforms [{\bf Y}_{{\bf m}'_{1}}^{*}] and [{\bf Y}_{{\bf m}''_{1}}^{*}] by using the Hermitian symmetry of the latter, which yields the demultiplexing formulae[\eqalign{Y_{{\bf m}'_{1}}^{*} ({\bf h}_{2}) + iY_{{\bf m}''_{1}}^{*} ({\bf h}_{2}) &= Y^{*} ({\bf h}_{2})\cr \overline{Y_{{\bf m}'_{1}}^{*} ({\bf h}_{2})} + \overline{iY_{{\bf m}''_{1}}^{*} ({\bf h}_{2})} &= Y^{*} [{\bf M} {\boldzeta} ({\bf h}_{2}) - {\bf h}_{2}].}]The number of partial transforms [\bar{F} ({\bf M})] is thus reduced from [2^{n}] to [2^{n - 1}]. Once this separation has been achieved, the remaining steps need only be carried out for a unique half of the values of [{\bf h}_{2}].

    • (ii) Decimation in frequency [({\bf N}_{1} = {\bf M},{\bf N}_{2} = 2{\bf I})]

      Since [{\bf h}_{2} \in {\bb Z}^{n} / 2{\bb Z}^{n}] we have [-{\bf h}_{2} = {\bf h}_{2}] and [{\boldzeta} ({\bf h}_{2}) = {\bf h}_{2}] mod [2{\bb Z}^{n}]. The vectors of decimated and scrambled results [{\bf Z}_{{\bf h}_{2}}^{*}] then obey the symmetry relations[Z_{{\bf h}_{2}}^{*} ({\bf h}_{1} - {\bf h}_{2}) = \overline{Z_{{\bf h}_{2}}^{*} [{\bf M} {\boldzeta} ({\bf h}_{1}) - {\bf h}_{1}]}]which can be used to halve the number of [\bar{F} ({\bf M})] necessary to compute them, as follows.

      Having formed the vectors [{\bf Z}_{{\bf h}_{2}}] given by[Z_{{\bf h}_{2}} ({\bf m}_{1}) = \left[\sum\limits_{{\bf m}_{2} \in {\bb Z}^{n} / 2{\bb Z}^{n}} {(-1)^{{\bf h}_{2} \cdot {\bf m}_{2}} \over 2^{n}} \rho\llap{$-\!$} ({\bf m}_{1} + {\bf Mm}_{2})\right] e[{\bf h}_{2} \cdot ({\bf N}^{-1} {\bf m}_{1})],]we may group the [2^{n}] values of [{\bf h}_{2}] into [2^{n - 1}] pairs [({\bf h}'_{2}, {\bf h}''_{2})] and for each pair form the multiplexed vector:[{\bf Z} = {\bf Z}_{{\bf h}'_{2}} + i{\bf Z}_{{\bf h}''_{2}}.]After calculating the [2^{n - 1}] transforms [{\bf Z}^{*} = \bar{F} ({\bf M}) [{\bf Z}]], the [2^{n}] individual transforms [{\bf Z}_{{\bf h}'_{2}}^{*}] and [{\bf Z}_{{\bf h}''_{2}}^{*}] can be separated by using for each pair the demultiplexing formulae[\eqalign{Z_{{\bf h}'_{2}}^{*} ({\bf h}_{1}) + iZ_{{\bf h}''_{2}}^{*} ({\bf h}_{1}) &= Z^{*} ({\bf h}_{1})\cr Z_{{\bf h}'_{2}}^{*} ({\bf h}_{1} - {\bf h}'_{2}) + iZ_{{\bf h}''_{2}}^{*} ({\bf h}_{1} - {\bf h}''_{2}) &= \overline{Z^{*} [{\bf M} {\boldzeta} ({\bf h}_{1}) - {\bf h}_{1}]}}]which can be solved recursively. If all pairs are chosen so that they differ only in the jth coordinate [({\bf h}_{2})_{j}], the recursion is along [({\bf h}_{1})_{j}] and can be initiated by introducing the (real) values of [Z_{{\bf h}'_{2}}^{*}] and [Z_{{\bf h}''_{2}}^{*}] at [({\bf h}_{1})_{j} = 0] and [({\bf h}_{1})_{j} = M_{j}], accumulated e.g. while forming Z for that pair. Only points with [({\bf h}_{1})_{j}] going from 0 to [{1 \over 2} M_{j}] 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:[{\bf F} {\buildrel{{\bf scr}({\bf N}_{2})} \over {\,\longmapsto\,}} {\bf Z}^{*} {\buildrel{F({\bf N}_{1})} \over {\,\longmapsto\,}} {\bf Z} {\buildrel{\scriptstyle{\rm TW}} \over {\,\longmapsto\,}} {\bf Y}^{*} {\buildrel{F({\bf N}_{2})} \over {\,\longmapsto\,}} {\bf Y} {\buildrel{{\bf nat}({\bf N}_{1})} \over {\,\longmapsto\,}} \rho\llap{$-\!$}]where [{\bf scr}({\bf N}_{2})] is the decimation with coset reversal given by [{\bf Z}_{{\bf h}_{2}}^{*} ({\bf h}_{1}) = F ({\bf h}_{2} + {\bf N}_{2} {\bf h}_{1})], TW is the transposition and twiddle-factor stage, and [{\bf nat}({\bf N}_{1})] is the recovery in natural order given by [\rho\llap{$-\!$} ({\bf m}_{1} + {\bf N}_{1} {\bf m}_{2}) = Y_{{\bf m}_{1}} ({\bf m}_{2})].

    • (i) Decimation in time [({\bf N}_{1} = {\bf M},{\bf N}_{2} = 2{\bf I})]

      The last transformation [F(2{\bf I})] has a real-valued matrix, and the final result [\rho\llap{$-\!$}] is real-valued. It follows that the vectors [{\bf Y}_{{\bf m}_{1}}^{*}] 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 [2^{n}] initial vectors [{\bf Z}_{{\bf h}_{2}}^{*}] be multiplexed into [2^{n - 1}] vectors[{\bf Z}^{*} = {\bf Z}_{{\bf h}'_{2}}^{*} + i{\bf Z}_{{\bf h}''_{2}}^{*}][one for each pair [({\bf h}'_{2}, {\bf h}''_{2})]], each of which yields by F(M) a vector[{\bf Z} = {\bf Z}_{{\bf h}'_{2}} + i{\bf Z}_{{\bf h}''_{2}}.]The real-valuedness of the [{\bf Y}_{{\bf m}_{1}}^{*}] may be used to recover the separate result vectors for [{\bf h}'_{2}] and [{\bf h}''_{2}]. For this purpose, introduce the abbreviated notation[\eqalign{&e[-{\bf h}'_{2} \cdot ({\bf N}^{-1} {\bf m}_{1})] = (c' + is') ({\bf m}_{1})\cr &e[-{\bf h}''_{2} \cdot ({\bf N}^{-1} {\bf m}_{1})] = (c'' + is'') ({\bf m}_{1})\cr &\qquad \quad R_{{\bf h}_{2}} ({\bf m}_{1}) = Y_{{\bf m}_{1}}^{*} ({\bf h}_{2})\cr &\qquad {\bf R}' = {\bf R}_{{\bf h}'_{2}},\quad {\bf R}'' = {\bf R}_{{\bf h}''_{2}}.}]Then we may write[\eqalign{{\bf Z} &= (c' + is') {\bf R}' + i(c'' + is'') {\bf R}''\cr &= (c' {\bf R}' + s'' {\bf R}'') + i(-s' {\bf R}' + c'' {\bf R}'')}]or, equivalently, for each [{\bf m}_{1}],[\pmatrix{{\scr Re} \,Z\cr {\scr Im}\,Z\cr} = \pmatrix{c' &s''\cr -s' &c''\cr} \pmatrix{R'\cr R''\cr}.]Therefore [{\bf R}'] and [{\bf R}''] may be retrieved from Z by the `demultiplexing' formula:[\pmatrix{R'\cr R''\cr} = {1 \over c' c'' + s' s''} \pmatrix{c'' &-s''\cr s' &c'\cr} \pmatrix{{\scr Re}\, Z\cr {\scr Im} \,Z\cr}]which is valid at all points [{\bf m}_{1}] where [c' c'' + s' s'' \neq 0], i.e. where[\cos [2 \pi ({\bf h}'_{2} - {\bf h}''_{2}) \cdot ({\bf N}^{-1} {\bf m}_{1})] \neq 0.]Demultiplexing fails when[({\bf h}'_{2} - {\bf h}''_{2}) \cdot ({\bf N}^{-1} {\bf m}_{1}) = {\textstyle{1 \over 2}} \hbox{ mod } 1.]If the pairs [({\bf h}'_{2}, {\bf h}''_{2})] are chosen so that their members differ only in one coordinate (the jth, say), then the exceptional points are at [({\bf m}_{1})_{j} = {1 \over 2} M_{j}] and the missing transform values are easily obtained e.g. by accumulation while forming [{\bf Z}^{*}].

      The final stage of the calculation is then[\rho\llap{$-\!$} ({\bf m}_{1} + {\bf Mm}_{2}) = {\textstyle\sum\limits_{{\bf h}_{2} \in {\bf Z}^{n} / 2{\bf Z}^{n}}} (-1)^{{\bf h}_{2} \cdot {\bf m}_{2}} R_{{\bf h}_{2}} ({\bf m}_{1}).]

    • (ii) Decimation in frequency [({\bf N}_{1} = 2{\bf I},{\bf N}_{2} = {\bf M})]

      The last transformation F(M) gives the real-valued results [\rho\llap{$-\!$}], therefore the vectors [{\bf Y}_{{\bf m}_{1}}^{*}] after the twiddle-factor stage each have Hermitian symmetry.

      A first consequence is that the intermediate vectors [{\bf Z}_{{\bf h}_{2}}] need only be computed for the unique half of the values of [{\bf h}_{2}], the other half being related by the Hermitian symmetry of [{\bf Y}_{{\bf m}_{1}}^{*}].

      A second consequence is that the [2^{n}] vectors [{\bf Y}_{{\bf m}_{1}}^{*}] may be condensed into [2^{n - 1}] general complex vectors[{\bf Y}^{*} = {\bf Y}_{{\bf m}'_{1}}^{*} + i{\bf Y}_{{\bf m}''_{1}}^{*}][one for each pair [({\bf m}'_{1}, {\bf m}''_{1})]] to which a general complex F(M) may be applied to yield[{\bf Y} = {\bf Y}_{{\bf m}'_{1}} + i{\bf Y}_{{\bf m}''_{1}}]with [{\bf Y}_{{\bf m}'_{1}}] and [{\bf Y}_{{\bf m}''_{1}}] real-valued. The final results can therefore be retrieved by the particularly simple demultiplexing formulae:[\eqalign{\rho\llap{$-\!$} ({\bf m}'_{1} + 2{\bf m}_{2}) &= {\scr Re} \,Y({\bf m}_{2}),\cr \rho\llap{$-\!$} ({\bf m}''_{1} + 2{\bf m}_{2}) &= {\scr Im}\, Y({\bf m}_{2}).}]

References

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








































to end of page
to top of page