Hermitian-symmetric or real-valued transforms

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-80 | 1 | 2 |

Section 1.3.4.3.5.1. Hermitian-symmetric or real-valued transforms

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