Tables for
Volume B
Reciprocal space
Edited by U. Shmueli

International Tables for Crystallography (2006). Vol. B, ch. 1.3, p. 81   | 1 | 2 |

Section Real symmetric transforms

G. Bricognea

aMRC Laboratory of Molecular Biology, Hills Road, Cambridge CB2 2QH, England, and LURE, Bâtiment 209D, Université Paris-Sud, 91405 Orsay, France Real symmetric transforms

| top | pdf |

Conjugate symmetric (Section[link]) 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[link](b)[link] 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[link](c)(i)[link], [\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 [(c' - is')] and [(c'' - is'')] 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 [c' s'' - s' c'' = 0] 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[link](c)[link]. 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[link](b)(ii)[link]. This yields the unique half of the real symmetric results F.

to end of page
to top of page