Treatment of conjugate and parity-related symmetry properties

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. 79-82 | 1 | 2 |

Section 1.3.4.3.5. Treatment of conjugate and parity-related symmetry properties

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.3.5. Treatment of conjugate and parity-related symmetry properties

| top | pdf |

Most crystallographic Fourier syntheses are real-valued and originate from Hermitian-symmetric collections of Fourier coefficients. Hermitian symmetry is closely related to the action of a centre of inversion in reciprocal space, and thus interacts strongly with all other genuinely crystallographic symmetry elements of order 2. All these symmetry properties are best treated by factoring by 2 and reducing the computation of the initial transform to that of a collection of smaller transforms with less symmetry or none at all.

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).

(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 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) 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) 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.

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}).}]$

1.3.4.3.5.2. Hermitian-antisymmetric or pure imaginary transforms

| top | pdf |

A vector $[{\bf X} = \{X ({\bf k}) | {\bf k} \in {\bb Z}^{n} / {\bf N}{\bb Z}^{n}\}]$ is said to be Hermitian-antisymmetric if $[X ({\bf k}) = -\overline{X (-{\bf k})} \hbox{ for all } {\bf k.}]$ Its transform $[{\bf X}^{*}]$ then satisfies $[X^{*} ({\bf k}^{*}) = -\overline{X^{*} ({\bf k}^{*})} \hbox{ for all } {\bf k}^{*},]$ i.e. is purely imaginary.

If X is Hermitian-antisymmetric, then $[{\bf F} = \pm i{\bf X}]$ is Hermitian-symmetric, with $[\rho\llap{$-\!$} = \pm i{\bf X}^{*}]$ real-valued. The treatment of Section 1.3.4.3.5.1 may therefore be adapted, with trivial factors of i or [-1] , or used as such in conjunction with changes of variable by multiplication by $[\pm i]$ .

1.3.4.3.5.3. Complex symmetric and antisymmetric transforms

| top | pdf |

The matrix $[-{\bf I}]$ is its own contragredient, and hence (Section 1.3.2.4.2.2) the transform of a symmetric (respectively antisymmetric) function is symmetric (respectively antisymmetric). In this case the group $[G = \{e, -e\}]$ acts in both real and reciprocal space as $[\{{\bf I}, -{\bf I}\}]$ . If $[{\bf N} = {\bf N}_{1} {\bf N}_{2}]$ with both factors diagonal, then [-e] acts by $[\eqalign{ ({\bf m}_{1}, {\bf m}_{2}) \;&\longmapsto\; [{\bf N}_{1} {\boldzeta} ({\bf m}_{1}) - {\bf m}_{1}, {\bf N}_{2} {\boldzeta} ({\bf m}_{2}) - {\bf m}_{2} - {\boldzeta} ({\bf m}_{1})],\cr ({\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})],}]$ i.e. $[\eqalign{{\boldmu}_{2} (-e, {\bf m}_{1}) &= -{\boldzeta} ({\bf m}_{1}) \hbox{ mod } {\bf N}_{2} {\bb Z}^{n},\cr {\boldeta}_{1} (-e, {\bf h}_{2}) &= -{\boldzeta} ({\bf h}_{2}) \hbox{ mod } {\bf N}_{1} {\bb Z}^{n}.}]$

The symmetry or antisymmetry properties of X may be written $[X (-{\bf m}) = -\varepsilon X ({\bf m}) \hbox{ for all } {\bf m},]$ with $[\varepsilon = + 1]$ for symmetry and $[\varepsilon = -1]$ for antisymmetry.

The computation will be summarized as $[{\bf X} {\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 X}^{*}]$ with the same indexing as that used for structure-factor calculation. In both cases it will be shown that a transform $[F({\bf N})]$ with $[{\bf N} = {\bf 2M}]$ and M diagonal can be computed using only $[2^{n-1}]$ partial transforms $[F({\bf M})]$ instead of $[2^{n}]$ .

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

Since $[{\bf m}_{1} \in {\bb Z}^{n}/2{\bb Z}^{n}]$ we have $[-{\bf m}_{1} = {\bf m}_{1}]$ and $[{\boldzeta} ({\bf m}_{1}) = {\bf m}_{1}]$ mod $[2{\bb Z}^{n}]$ , so that the symmetry relations for each parity class of data $[{\bf Y}_{{\bf m}_{1}}]$ read $[Y_{{\bf m}_{1}} [{\bf M} {\boldzeta} ({\bf m}_{2}) - {\bf m}_{2} - {\bf m}_{1}] = \varepsilon Y_{{\bf m}_{1}} ({\bf m}_{2})]$ or equivalently $[\tau_{{\bf m}_{1}} {\bf Y}_{{\bf m}_{1}} = \varepsilon \breve{{\bf Y}}_{{\bf m}_{1}}.]$ Transforming by $[F({\bf M})]$ , this relation becomes $[e [-{\bf h}_{2} \cdot ({\bf M}^{-1} {\bf m}_{1})] {\bf Y}_{{\bf m}_{1}}^{*} = \varepsilon {\bf Y}_{{\bf m}_{1}}^{*}.]$ Each parity class thus obeys a different symmetry relation, so that we may multiplex them in pairs by forming for each pair $[({\bf m}'_{1}, {\bf m}''_{1})]$ the vector $[{\bf Y} = {\bf Y}_{{\bf m}'_{1}} + {\bf Y}_{{\bf m}''_{1}}.]$ Putting $[\eqalign{e [-{\bf h}_{2} \cdot ({\bf M}^{-1} {\bf m}'_{1})] &= (c' + is') ({\bf h}_{2})\cr e [-{\bf h}_{2} \cdot ({\bf M}^{-1} {\bf m}''_{1})] &= (c'' + is'') ({\bf h}_{2})}]$ we then have the demultiplexing relations for each $[{\bf h}_{2}]$ : $[\displaylines{Y_{{\bf m}'_{1}}^{*} ({\bf h}_{2}) + Y_{{\bf m}''_{1}}^{*} ({\bf h}_{2})= Y^{*} ({\bf h}_{2})\cr (c' + is') ({\bf h}_{2}) Y_{{\bf m}'_{1}}^{*} ({\bf h}_{2}) + (c'' + is'') ({\bf h}_{2})Y_{{\bf m}''_{1}}^{*} ({\bf h}_{2})\cr \qquad\qquad\quad\; = \varepsilon Y^{*} [{\bf M} \boldzeta ({\bf h}_{2}) - {\bf h}_{2}]\hfill}]$ which can be solved recursively. Transform values at the exceptional points $[{\bf h}_{2}]$ where demultiplexing fails (i.e. where ) can be accumulated while forming Y.

Only the unique half of the values of $[{\bf h}_{2}]$ need to be considered at the demultiplexing stage and at the subsequent TW and F(2I) stages.
(ii) Decimation in frequency $[({\bf N}_{1} = {\bf M},{\bf N}_{2} = 2{\bf I})]$

The vectors of final results $[{\bf Z}_{{\bf h}_{2}}^{*}]$ for each parity class $[{\bf h}_{2}]$ obey the symmetry relations $[\tau_{{\bf h}_{2}} {\bf Z}_{{\bf h}_{2}}^{*} = \varepsilon \check{{\bf Z}}_{{\bf h}_{2}}^{*},]$ which are different for each $[{\bf h}_{2}]$ . The vectors $[{\bf Z}_{{\bf h}_{2}}]$ of intermediate results after the twiddle-factor stage may then be multiplexed in pairs as $[{\bf Z} = {\bf Z}_{{\bf h}'_{2}} + {\bf Z}_{{\bf h}''_{2}}.]$

After transforming by $[F({\bf M})]$ , the results $[{\bf Z}^{*}]$ may be demultiplexed by using the relations $[\eqalign{Z_{{\bf h}'_{2}}^{*} ({\bf h}_{1})\quad &+ Z_{{\bf h}''_{2}}^{*} ({\bf h}_{1}) \phantom{- {\bf h}''_{2})} = Z^{*} ({\bf h}_{1})\cr Z_{{\bf h}'_{2}}^{*} ({\bf h}_{1} - {\bf h}'_{2}) &+ Z_{{\bf h}''_{2}}^{*} ({\bf h}_{1} - {\bf h}''_{2}) = \varepsilon Z^{*} [{\bf M} \boldzeta ({\bf h}_{1}) - {\bf h}_{1}]}]$ which can be solved recursively as in Section 1.3.4.3.5.1(b)(ii).

1.3.4.3.5.4. Real symmetric transforms

| top | pdf |

Conjugate symmetric (Section 1.3.2.4.2.3) implies that if the data X are real and symmetric [i.e. $[X({\bf k}) = \overline{X({\bf k})}]$ and $[X (- {\bf k}) = X ({\bf k})]$ ], then so are the results $[{\bf X}^{*}]$ . Thus if $[\rho\llap{$-\!$}]$ contains a centre of symmetry, F is real symmetric. There is no distinction (other than notation) between structure-factor and electron-density calculation; the algorithms will be described in terms of the former. It will be shown that if $[{\bf N} = 2{\bf M}]$ , a real symmetric transform can be computed with only $[2^{n-2}]$ partial transforms $[F({\bf M})]$ instead of $[2^{n}]$ .

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

Since $[{\bf m}_{1} \in {\bb Z}^{n}/2{\bb Z}^{n}]$ we have $[-{\bf m}_{1} = {\bf m}_{1}]$ and $[{\boldzeta} ({\bf m}_{1})=]$ $[ {\bf m}_{1} \hbox{ mod } 2{\bb Z}^{n}]$ . The decimated vectors $[{\bf Y}_{{\bf m}_{1}}]$ are not only real, but have an internal symmetry expressed by $[{\bf Y}_{{\bf m}_{1}} [{\bf M} {\boldzeta} ({\bf m}_{2}) - {\bf m}_{2} - {\bf m}_{1}] = \varepsilon {\bf Y}_{{\bf m}_{1}} ({\bf m}_{2}).]$ This symmetry, however, is different for each $[{\bf m}_{1}]$ so that we may multiplex two such vectors $[{\bf Y}_{{\bf m}'_{1}}]$ and $[{\bf Y}_{{\bf m}''_{1}}]$ into a general real vector $[{\bf Y} = {\bf Y}_{{\bf m}'_{1}} + {\bf Y}_{{\bf m}''_{1}},]$ for each of the $[2^{n-1}]$ pairs $[({\bf m}'_{1}, {\bf m}''_{1})]$ . The $[2^{n-1}]$ Hermitian-symmetric transform vectors $[{\bf Y}^{*} = {\bf Y}_{{\bf m}'_{1}}^{*} + {\bf Y}_{{\bf m}''_{1}}^{*}]$ can then be evaluated by the methods of Section 1.3.4.3.5.1(b) at the cost of only $[2^{n-2}]$ general complex $[F({\bf M})]$ .

The demultiplexing relations by which the separate vectors $[{\bf Y}_{{\bf m}'_{1}}^{*}]$ and $[{\bf Y}_{{\bf m}''_{1}}^{*}]$ may be recovered are most simply obtained by observing that the vectors Z after the twiddle-factor stage are real-valued since F(2I) has a real matrix. Thus, as in Section 1.3.4.3.5.1(c)(i), $[\eqalign{{\bf Y}_{{\bf m}'_{1}}^{*} &= (c' - is') {\bf R}'\cr {\bf Y}_{{\bf m}''_{1}}^{*} &= (c'' - is'') {\bf R}'',}]$ where $[{\bf R}']$ and $[{\bf R}'']$ are real vectors and where the multipliers and are the inverse twiddle factors. Therefore, $[\eqalign{{\bf Y}^{*} &= (c' - is') {\bf R}' + (c'' - is'') {\bf R}''\cr &= (c' {\bf R}' + c'' {\bf R}'') - i(s' {\bf R}' + s'' {\bf R}'')}]$ and hence the demultiplexing relation for each $[{\bf h}_{2}]$ : $[\pmatrix{R'\cr R''\cr} = {1 \over c' s'' - s' c''} \pmatrix{s'' &-c''\cr -s' &c'\cr} \pmatrix{{\scr Re}\; Y^{*}\cr -{\scr Im} \;Y^{*}\cr}.]$ The values of $[R'_{{\bf h}_{2}}]$ and $[R''_{{\bf h}_{2}}]$ at those points $[{\bf h}_{2}]$ where can be evaluated directly while forming Y. This demultiplexing and the final stage of the calculation, namely $[F ({\bf h}_{2} + {\bf Mh}_{1}) = {1 \over 2^{n}} \sum\limits_{{\bf m}_{1} \in {\bf Z}^{n}/2{\bf Z}^{n}} (-1)^{{\bf h}_{1} \cdot {\bf m}_{1}} R_{{\bf m}_{1}} ({\bf h}_{2})]$ need only be carried out for the unique half of the range of $[{\bf h}_{2}]$ .
(ii) Decimation in frequency $[({\bf N}_{1} = {\bf M}, {\bf N}_{2} = 2{\bf I})]$

Similarly, the vectors $[{\bf Z}_{{\bf h}_{2}}^{*}]$ of decimated and scrambled results are real and obey internal symmetries $[\tau_{{\bf h}_{2}} {\bf Z}_{{\bf h}_{2}}^{*} = \varepsilon \breve{{\bf Z}}_{{\bf h}_{2}}^{*}]$ which are different for each $[{\bf h}_{2}]$ . For each of the $[2^{n-1}]$ pairs $[({\bf h}'_{2}, {\bf h}''_{2})]$ the multiplexed vector $[{\bf Z} = {\bf Z}_{{\bf h}'_{2}} + {\bf Z}_{{\bf h}''_{2}}]$ is a Hermitian-symmetric vector without internal symmetry, and the $[2^{n-1}]$ real vectors $[{\bf Z}^{*} = {\bf Z}_{{\bf h}'_{2}}^{*} + {\bf Z}_{{\bf h}''_{2}}^{*}]$ may be evaluated at the cost of only $[2^{n-2}]$ general complex $[F({\bf M})]$ by the methods of Section 1.3.4.3.5.1(c). The individual transforms $[{\bf Z}_{{\bf h}'_{2}}]$ and $[{\bf Z}_{{\bf h}''_{2}}]$ may then be retrieved via the demultiplexing relations $[\eqalign{&Z_{{\bf h}'_{2}}^{*} ({\bf h}_{1})\;\,\phantom{ - {\bf h}'_{2}} + Z_{{\bf h}''_{2}}^{*} ({\bf h}_{1})\,\phantom{-{\bf h}''_{2}) } = Z^{*} ({\bf h}_{1})\cr &Z_{{\bf h}'_{2}}^{*} ({\bf h}_{1} - {\bf h}'_{2}) + Z_{{\bf h}''_{2}}^{*} ({\bf h}_{1} - {\bf h}''_{2}) = Z^{*} [{\bf M} \boldzeta ({\bf h}_{1}) - {\bf h}_{1}]}]$ which can be solved recursively as described in Section 1.3.4.3.5.1(b)(ii). This yields the unique half of the real symmetric results F.

1.3.4.3.5.5. Real antisymmetric transforms

| top | pdf |

If X is real antisymmetric, then its transform $[{\bf X}^{*}]$ is purely imaginary and antisymmetric. The double-multiplexing techniques used for real symmetric transforms may therefore be adapted with only minor changes involving signs and factors of i.

1.3.4.3.5.6. Generalized multiplexing

| top | pdf |

So far the multiplexing technique has been applied to pairs of vectors with similar types of parity-related and/or conjugate symmetry properties, in particular the same value of ɛ.

It can be generalized so as to accommodate mixtures of vectors with different symmetry characteristics. For example if $[{\bf X}_{1}]$ is Hermitian-symmetric and $[{\bf X}_{2}]$ is Hermitian-antisymmetric, so that $[{\bf X}_{1}^{*}]$ is real-valued while $[{\bf X}_{2}^{*}]$ has purely imaginary values, the multiplexing process should obviously form $[{\bf X} = {\bf X}_{1} + {\bf X}_{2}]$ (instead of $[{\bf X} = {\bf X}_{1} + i{\bf X}_{2}]$ if both had the same type of symmetry), and demultiplexing consists in separating $[\eqalign{ {\bf X}_{1}^{*} &= {\scr Re}\; {\bf X}^{*}\cr {\bf X}_{2}^{*} &= i{\scr Im}\;{\bf X}^{*}.}]$

The general multiplexing formula for pairs of vectors may therefore be written $[{\bf X} = {\bf X}_{1} + \omega {\bf X}_{2},]$ where ω is a phase factor (e.g. 1 or i) chosen in such a way that all non-exceptional components of $[{\bf X}_{1}]$ and $[{\bf X}_{2}]$ (or $[{\bf X}_{1}^{*}]$ and $[{\bf X}_{2}^{*}]$ ) be embedded in the complex plane $[{\bb C}]$ along linearly independent directions, thus making multiplexing possible.

It is possible to develop a more general form of multiplexing/demultiplexing for more than two vectors, which can be used to deal with symmetry elements of order 3, 4 or 6. It is based on the theory of group characters (Ledermann, 1987).

References

Ledermann, W. (1987). Introduction to group characters, 2nd ed. Cambridge University Press.Google Scholar

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

International Tables for Crystallography (2006). Vol. B. ch. 1.3, pp. 79-82