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

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

Section 1.3.4.3.4.2. Multidimensional Good factorization

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.4.2. Multidimensional Good factorization

| top | pdf |

This procedure was described in Section 1.3.3.3.2.2[link]. The main difference with the Cooley–Tukey factorization is that if [{\bf N} = {\bf N}_{1}{\bf N}_{2} \ldots {\bf N}_{d-1} {\bf N}_{d}], where the different factors are pairwise coprime, then the Chinese remainder theorem reindexing makes [{\bb Z}^{3}/{\bf N}{\bb Z}^{3}] isomorphic to a direct sum.[{\bb Z}^{3}/{\bf N}{\bb Z}^{3} \cong ({\bb Z}^{3}/{\bf N}_{1}{\bb Z}^{3}) \oplus \ldots \oplus ({\bb Z}^{3}/{\bf N}_{d}{\bb Z}^{3}),]where each p-primary piece is endowed with an induced [{\bb Z}G]-module structure by letting G operate in the usual way but with the corresponding modular arithmetic. The situation is thus more favourable than with the Cooley–Tukey method, since there is no interference between the factors (no `carry'). In the terminology of Section 1.3.4.2.2.2[link], G acts diagonally on this direct sum, and results of a partial transform may be transposed by orbit exchange as in Section 1.3.4.3.4.1[link] but without the extra terms μ or η. The analysis of the symmetry properties of partial transforms also carries over, again without the extra terms. Further simplification occurs for all p-primary pieces with p other than 2 or 3, since all nonprimitive translations (including those associated to lattice centring) disappear modulo p.

Thus the cost of the CRT reindexing is compensated by the computational savings due to the absence of twiddle factors and of other phase shifts associated with nonprimitive translations and with geometric `carries'.

Within each p-primary piece, however, higher powers of p may need to be split up by a Cooley–Tukey factorization, or carried out directly by a suitably adapted Winograd algorithm.








































to end of page
to top of page