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

International Tables for Crystallography (2010). Vol. B, ch. 1.3, pp. 79-85   | 1 | 2 |

Section 1.3.4.3.4. Interaction between symmetry and 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. Interaction between symmetry and factorization

| top | pdf |

Methods for factoring the DFT in the absence of symmetry were examined in Sections 1.3.3.2[link] and 1.3.3.3[link]. They are based on the observation that the finite sets which index both data and results are endowed with certain algebraic structures (e.g. are Abelian groups, or rings), and that subsets of indices may be found which are not merely subsets but substructures (e.g. subgroups or subrings). Summation over these substructures leads to partial transforms, and the way in which substructures fit into the global structure indicates how to reassemble the partial results into the final results. As a rule, the richer the algebraic structure which is identified in the indexing set, the more powerful the factoring method.

The ability of a given factoring method to accommodate crystallographic symmetry will thus be determined by the extent to which the crystallographic group action respects (or fails to respect) the partitioning of the index set into the substructures pertaining to that method. This remark justifies trying to gain an overall view of the algebraic structures involved, and of the possibilities of a crystallographic group acting `naturally' on them.

The index sets [\{{\bf m} | {\bf m} \in {\bb Z}^{3}/{\bf N}{\bb Z}^{3}\}] and [\{{\bf h} | {\bf h} \in {\bb Z}^{3}/{\bf N}^{T} {\bb Z}^{3}\}] are finite Abelian groups under component-wise addition. If an iterated addition is viewed as an action of an integer scalar [n \in {\bb Z}] via[\matrix{n{\bf h} = {\bf h} + {\bf h} + \ldots + {\bf h}\hfill & (n \hbox{ times})\hfill & \hbox{for } n \,\gt\, 0,\hfill \cr \phantom{n{\bf h}}= {\bf 0}\hfill & & \hbox{for } n = 0,\hfill \cr \phantom{n{\bf h}}= -({\bf h} + {\bf h} + \ldots + {\bf h})\hfill &(|n| \hbox{ times})\hfill &\hbox{for } n \,\lt\, 0,\hfill}]then an Abelian group becomes a module over the ring [{\bb Z}] (or, for short, a [{\bb Z}]-module), a module being analogous to a vector space but with scalars drawn from a ring rather than a field. The left actions of a crystallographic group G by[\displaylines{g: \quad {\bf m} \,\longmapsto\, {\bf R}_{g} {\bf m} + {\bf Nt}_{g} \quad \hbox{mod } {\bf N}{\bb Z}^{3}\cr \hbox{and by}\hfill\cr \,\,g: \quad {\bf h} \,\longmapsto\, ({\bf R}_{g}^{-1})^{T} {\bf h} {\hbox to 22.5pt{}}\hbox{mod } {\bf N}^{T} {\bb Z}^{3}}]can be combined with this [{\bb Z}] action as follows:[\displaylines{\quad {\textstyle\sum\limits_{g \in G}} n_{g} g:\qquad {\bf m} \,\longmapsto\, {\textstyle\sum\limits_{g \in G}} n_{g} ({\bf R}_{g} {\bf m} + {\bf Nt}_{g})\qquad \hbox{ mod } {\bf N}{\bb Z}^{3},\hfill\cr \quad {\textstyle\sum\limits_{g \in G}} n_{g} g:\qquad {\bf h} \,\longmapsto\, {\textstyle\sum\limits_{g \in G}} n_{g} [({\bf R}_{g}^{-1})^{T} {\bf h}] {\hbox to 15pt{}} \phantom{\hbox{mod } {\bf}} \hbox{ mod } {\bf N}^{T} {\bb Z}^{3}.\hfill\cr}]This provides a left action, on the indexing sets, of the set[{\bb Z} G = \left\{{\textstyle\sum\limits_{g \in G}} n_{g} g\big| n_{g} \in {\bb Z} \hbox{ for each } g \in G\right\}]of symbolic linear combinations of elements of G with integral coefficients. If addition and multiplication are defined in [{\bb Z}G] by[\left({\textstyle\sum\limits_{g_{1} \in G}} a_{g_{1}} g_{1}\right) + \left({\textstyle\sum\limits_{g_{2} \in G}} b_{g_{2}} g_{2}\right) = {\textstyle\sum\limits_{g \in G}} (a_{g} + b_{g})g]and[\left({\textstyle\sum\limits_{g_{1} \in G}} a_{g_{1}} g_{1}\right) \times \left({\textstyle\sum\limits_{g_{2} \in G}} b_{g_{2}} g_{2}\right) = {\textstyle\sum\limits_{g \in G}} c_{g} g,]with[c_{g} = {\textstyle\sum\limits_{g' \in G}} a_{g'} b_{(g')^{-1}} g,]then [{\bb Z}G] is a ring, and the action defined above makes the indexing sets into [{\bb Z}G]-modules. The ring [{\bb Z}G] is called the integral group ring of G (Curtis & Reiner, 1962[link], p. 44).

From the algebraic standpoint, therefore, the interaction between symmetry and factorization can be expected to be favourable whenever the indexing sets of partial transforms are [{\bb Z}G]-submodules of the main [{\bb Z}G]-modules.

1.3.4.3.4.1. Multidimensional Cooley–Tukey factorization

| top | pdf |

Suppose, as in Section 1.3.3.3.2.1[link], that the decimation matrix N may be factored as [{\bf N}_{1} {\bf N}_{2}]. Then any grid point index [{\bf m} \in {\bb Z}^{3}/{\bf N} {\bb Z}^{3}] in real space may be written[{\bf m} = {\bf m}_{1} + {\bf N}_{1} {\bf m}_{2}]with [{\bf m}_{1} \in {\bb Z}^{3}/{\bf N}_{1} {\bb Z}^{3}] and [{\bf m}_{2} \in {\bb Z}^{3}/{\bf N}_{2} {\bb Z}^{3}] determined by[\let\normalbaselines\relax\openup4pt\matrix{ {\bf m}_{1} = {\bf m}\hfill &\hbox{ mod } {\bf N}_{1} {\bb Z}^{3},\hfill\cr {\bf m}_{2} = {\bf N}_{1}^{-1} ({\bf m} - {\bf m}_{1})\hfill &\hbox{ mod } {\bf N}_{2} {\bb Z}^{3}.\hfill}]These relations establish a one-to-one correspondence [{\bf m} \leftrightarrow ({\bf m}_{1}, {\bf m}_{2})] between [I = {\bb Z}^{3}/{\bf N} {\bb Z}^{3}] and the Cartesian product [I_{1} \times I_{2}] of [I_{1} = {\bb Z}^{3}/{\bf N}_{1} {\bb Z}^{3}] and [I_{2} = {\bb Z}^{3}/{\bf N}_{2} {\bb Z}^{3}], and hence [I \cong I_{1} \times I_{2}] as a set. However [I \not \cong I_{1} \times I_{2}] as an Abelian group, since in general [{\bf m} + {\bf m}'\,\, {\not{\hbox to -7pt{}}\longleftrightarrow} ({\bf m}_{1} + {\bf m}'_{1}, {\bf m}_{2} + {\bf m}'_{2})] because there can be a `carry' from the addition of the first components into the second components; therefore, [I \not \cong I_{1} \times I_{2}] as a [{\bb Z}G]-module, which shows that the incorporation of symmetry into the Cooley–Tukey algorithm is not a trivial matter.

Let [g \in G] act on I through[g: \quad {\bf m} \,\longmapsto\, S_{g} ({\bf m}) = {\bf R}_{g} {\bf m} + {\bf Nt}_{g} \hbox{ mod } {\bf N}{\bb Z}^{3}]and suppose that N `integerizes' all the nonprimitive translations [{\bf t}_{g}] so that we may write[{\bf Nt}_{g} = {\bf t}_{g}^{(1)} + {\bf N}_{1} {\bf t}_{g}^{(2)},]with [{\bf t}_{g}^{(1)} \in I_{1}] and [{\bf t}_{g}^{(2)} \in I_{2}] determined as above. Suppose further that N, [{\bf N}_{1}] and [{\bf N}_{2}] commute with [{\bf R}_{g}] for all [g \in G], i.e. (by Schur's lemma, Section 1.3.4.2.2.4[link]) that these matrices are integer multiples of the identity in each G-invariant subspace. The action of g on [{\bf m} = {\bf Nx} \hbox{ mod } {\bf N}{\bb Z}^{3}] leads to[\let\normalbaselines\relax\openup4pt\matrix{S_{g} ({\bf m}) = {\bf N} [{\bf R}_{g} ({\bf N}^{-1} {\bf m}) + {\bf Nt}_{g}]\hfill &\hbox{ mod } {\bf N}{\bb Z}^{3}\hfill \cr \phantom{S_{g} ({\bf m})}= {\bf NR}_{g} {\bf N}^{-1} ({\bf m}_{1} + {\bf N}_{1} {\bf m}_{2}) + {\bf t}_{g}^{(1)} + {\bf N}_{1} {\bf t}_{g}^{(2)}\hfill &\hbox{ mod } {\bf N}{\bb Z}^{3}\hfill \cr \phantom{S_{g} ({\bf m})}= {\bf R}_{g} {\bf m}_{{1}} + {\bf t}_{g}^{(1)} + {\bf N}_{1} ({\bf R}_{g} {\bf m}_{2} + {\bf t}_{g}^{(2)})\hfill &\hbox{ mod } {\bf N}{\bb Z}^{3},\hfill}]which we may decompose as[S_{g} ({\bf m}) = [S_{g} ({\bf m})]_{1} + {\bf N}_{1} [S_{g} ({\bf m})]_{2}]with[[S_{g} ({\bf m})]_{1} \equiv S_{g} ({\bf m}) \qquad\hbox{mod } {\bf N}_{1}{\bb Z}^{3}]and[[S_{g} ({\bf m})]_{2} \equiv {\bf N}_{1}^{-1} \{S_{g} ({\bf m}) - [S_{g} ({\bf m})]_{1}\} \qquad\hbox{mod } {\bf N}_{2}{\bb Z}^{3}.]

Introducing the notation[\eqalign{ S_{g}^{(1)} ({\bf m}_{1}) &= {\bf R}_{g} {\bf m}_{1} + {\bf t}_{g}^{(1)} \hbox{ mod } {\bf N}_{1}{\bb Z}^{3},\cr S_{g}^{(2)} ({\bf m}_{2}) &= {\bf R}_{g} {\bf m}_{2} + {\bf t}_{g}^{(2)} \hbox{ mod } {\bf N}_{2}{\bb Z}^{3},}]the two components of [S_{g} ({\bf m})] may be written[\eqalign{ [S_{g} ({\bf m})]_{1} &= S_{g}^{(1)} ({\bf m}_{1}),\cr [S_{g} ({\bf m})]_{2} &= S_{g}^{(2)} ({\bf m}_{2}) + {\boldmu}_{2} (g, {\bf m}_{1}) \hbox{ mod } {\bf N}_{2}{\bb Z}^{3},}]with[{\boldmu}_{2} (g, {\bf m}_{1}) = {\bf N}_{1}^{-1} \{({\bf R}_{g} {\bf m}_{1} + {\bf t}_{g}^{(1)}) - [S_{g} ({\bf m}_{1})]_{1}\} \hbox{ mod } {\bf N}_{2}{\bb Z}^{3}.]

The term [\boldmu_{2}] is the geometric equivalent of a carry or borrow: it arises because [{\bf R}_{g} {\bf m}_{1} + {\bf t}_{g}^{(1)}], calculated as a vector in [{\bb Z}^{3}/{\bf N}{\bb Z}^{3}], may be outside the unit cell [{\bf N}_{1} [0, 1]^{3}], and may need to be brought back into it by a `large' translation with a nonzero component in the [{\bf m}_{2}] space; equivalently, the action of g may need to be applied around different permissible origins for different values of [{\bf m}_{1}], so as to map the unit cell into itself without any recourse to lattice translations. [Readers familiar with the cohomology of groups (see e.g. Hall, 1959[link]; MacLane, 1963[link]) will recognize [\boldmu_{2}] as the cocycle of the extension of [{\bb Z}] G-modules described by the exact sequence [0 \rightarrow I_{2} \rightarrow I \rightarrow I_{1} \rightarrow 0].]

Thus G acts on I in a rather complicated fashion: although [g \,\longmapsto\, S_{g}^{(1)}] does define a left action in [I_{1}] alone, no action can be defined in [I_{2}] alone because [\boldmu_{2}] depends on [{\bf m}_{1}]. However, because [S_{g}], [S_{g}^{(1)}] and [S_{g}^{(2)}] are left actions, it follows that [\boldmu_{2}] satisfies the identity[{\boldmu}_{2} (gg', {\bf m}_{1}) = S_{g}^{(2)} [{\boldmu}_{2} (g', {\bf m}_{1})] + {\boldmu}_{2} [g, S_{g}^{(1)} ({\bf m}_{1})] \qquad\hbox{mod } {\bf N}_{2} {\bb Z}^{3}]for all g, [g'] in G and all [{\bf m}_{1}] in [I_{1}]. In particular, [\boldmu_{2} (\hbox{e}, {\bf m}_{1}) = {\bf 0}] for all [{\bf m}_{1}], and[{\boldmu}_{2} (g^{-1}, {\bf m}_{1}) = -S_{g^{-1}}^{(2)} \{{\boldmu}_{2} [g, S_{g^{-1}}^{(1)} ({\bf m}_{1})]\} \hbox{ mod } {\bf N}_{2} {\bb Z}^{3}.]

This action will now be used to achieve optimal use of symmetry in the multidimensional Cooley–Tukey algorithm of Section 1.3.3.3.2.1.[link] Let us form an array Y according to[Y({\bf m}_{1}, {\bf m}_{2}) = \rho ({\bf m}_{1} + {\bf N}_{1} {\bf m}_{2})]for all [{\bf m}_{2} \in I_{2}] but only for the unique [{\bf m}_{1}] under the action [S_{g}^{(1)}] of G in [I_{1}]. Except in special cases which will be examined later, these vectors contain essentially an asymmetric unit of electron-density data, up to some redundancies on boundaries. We may then compute the partial transform on [{\bf m}_{2}]:[Y^{*} ({\bf m}_{1}, {\bf h}_{2}) = {1 \over |\hbox{det } {\bf N}_{2}|} {\sum\limits_{{\bf m}_{2} \in I_{2}}} Y({\bf m}_{1}, {\bf m}_{2}) e[{\bf h}_{2} \cdot ({\bf N}_{2}^{-1} {\bf m}_{2})].]Using the symmetry of [\rho\llap{$-\!$}] in the form [\rho\llap{$-\!$} = S_{g}^{\#} \rho\llap{$-\!$}] yields by the procedure of Section 1.3.3.3.2[link] the transposition formula[\eqalign{ Y^{*} (S_{g}^{(1)} ({\bf m}_{1}), {\bf h}_{2}) &= e\{{\bf h}_{2} \cdot [{\bf N}_{2}^{-1} ({\bf t}_{g}^{(2)} + {\boldmu}_{2} (g, {\bf m}_{1}))]\}\cr &\quad \times Y^{*} ({\bf m}_{1}, [{\bf R}_{g}^{(2)}]^{T} {\bf h}_{2}).}]

By means of this identity we can transpose intermediate results [Y^{*}] initially indexed by[(\hbox{unique } {\bf m}_{1}) \times (\hbox{all } {\bf h}_{2}),]so as to have them indexed by[(\hbox{all } {\bf m}_{1}) \times (\hbox{unique } {\bf h}_{2}).]We may then apply twiddle factors to get[Z({\bf m}_{1}, {\bf h}_{2}) = e[{\bf h}_{2} \cdot ({\bf N}^{-1} {\bf m}_{1})] Y^{*} ({\bf m}_{1}, {\bf h}_{2})]and carry out the second transform[Z^{*} ({\bf h}_{1}, {\bf h}_{2}) = {1 \over |\hbox{det } {\bf N}_{1}|} {\sum\limits_{{\bf m}_{1} \in I_{1}}} Z({\bf m}_{1}, {\bf h}_{2}) e[{\bf h}_{1} \cdot ({\bf N}_{1}^{-1} {\bf m}_{1})].]The final results are indexed by[(\hbox{all } {\bf h}_{1}) \times (\hbox{unique } {\bf h}_{2}),]which yield essentially an asymmetric unit of structure factors after unscrambling by:[F({\bf h}_{2} + {\bf N}_{2}^{T} {\bf h}_{1}) = Z^{*} ({\bf h}_{1}, {\bf h}_{2}).]

The transposition formula above applies to intermediate results when going backwards from F to [\rho\llap{$-\!$}], provided these results are considered after the twiddle-factor stage. A transposition formula applicable before that stage can be obtained by characterizing the action of G on h (including the effects of periodization by [{\bf N}^{T} {\bb Z}^{3}]) in a manner similar to that used for m.

Let[{\bf h} = {\bf h}_{2} + {\bf N}_{2}^{T} {\bf h}_{1},]with[\let\normalbaselines\relax\openup4pt\matrix{{\bf h}_{2} = {\bf h}\hfill &\hbox{mod } {\bf N}_{2}^{T} {\bb Z}^{3},\hfill \cr {\bf h}_{1} = ({\bf N}_{2}^{-1})^{T} ({\bf h} - {\bf h}_{2}) \hfill & \hbox{mod } {\bf N}_{1}^{T} {\bb Z}^{3}.\hfill}]We may then write[{\bf R}_{g}^{T} {\bf h} = [{\bf R}_{g}^{T} {\bf h}]_{2} + {\bf N}_{2}^{T} [{\bf R}_{g}^{T} {\bf h}]_{1},]with[\let\normalbaselines\relax\openup4pt\matrix{ [{\bf R}_{g}^{T} {\bf h}]_{2} = [{\bf R}_{g}^{(2)}]^{T} {\bf h}_{2} \hfill &\hbox{mod } {\bf N}_{2}^{T} {\bb Z}^{3},\hfill \cr [{\bf R}_{g}^{T} {\bf h}]_{1} = [{\bf R}_{g}^{(1)}]^{T} {\bf h}_{1} + {\boldeta}_{1} (g, {\bf h}_{2}) \hfill &\hbox{mod } {\bf N}_{1}^{T} {\bb Z}^{3}.\hfill}]Here [[{\bf R}_{g}^{(2)}]^{T}, [{\bf R}_{g}^{(1)}]^{T}] and [\boldeta_{1}] are defined by[\eqalign{ [{\bf R}_{g}^{(2)}]^{T} {\bf h}_{2} &= {\bf R}_{g}^{T} {\bf h}\quad \quad \hbox{ mod } {\bf N}_{2}^{T} {\bb Z}^{3},\cr [{\bf R}_{g}^{(1)}]^{T} {\bf h}_{1} &= {\bf R}_{g}^{T} {\bf h}\quad \quad \hbox{ mod } {\bf N}_{1}^{T} {\bb Z}^{3}}]and[{\boldeta}_{1} (g, {\bf h}_{2}) = ({\bf N}_{2}^{-1})^{T} ({\bf R}_{g}^{T} {\bf h}_{2} - [{\bf R}_{g}^{(2)}]^{T} {\bf h}_{2}) \hbox{ mod } {\bf N}_{1}^{T} {\bb Z}^{3}.]

Let us then form an array [Z^{*}] according to[Z^{*} ({\bf h}'_{1}, {\bf h}'_{2}) = F({\bf h}'_{2} + {\bf N}_{2}^{T} {\bf h}'_{1})]for all [{\bf h}'_{1}] but only for the unique [{\bf h}'_{2}] under the action of G in [{\bb Z}^{3} / {\bf N}_{2}^{T} {\bb Z}^{3}], and transform on [{\bf h}'_{1}] to obtain[Z({\bf m}_{1}, {\bf h}_{2}) = {\textstyle\sum\limits_{{\bf h}'_{1} \in {\bb Z}^{3} / {\bf N}_{1}^{T} {\bb Z}^{3}}} Z^{*}({\bf h}'_{1}, {\bf h}'_{2}) e[-{\bf h}'_{1} \cdot ({\bf N}_{1}^{-1} {\bf m}_{1})].]Putting [{\bf h}' = {\bf R}_{g}^{T}{\bf h}] and using the symmetry of F in the form[F({\bf h}') = F({\bf h}) \exp (-2\pi i{\bf h} \cdot {\bf t}_{g}),]where[\eqalign{ {\bf h} \cdot {\bf t}_{g} &= ({\bf h}_{2}^{T} + {\bf h}_{1}^{T} {\bf N}_{2}) ({\bf N}_{2}^{-1} {\bf N}_{1}^{-1}) ({\bf t}_{g}^{(1)} + {\bf N}_{1} {\bf t}_{g}^{(2)})\cr &\equiv {\bf h}_{2} \cdot {\bf t}_{g} + {\bf h}_{2} \cdot ({\bf N}_{1}^{-1} {\bf t}_{g}^{(1)}) \hbox{ mod } 1}]yields by a straightforward rearrangement[\eqalign{Z({\bf m}_{1}, [{\bf R}_{g}^{(2)}]^{T} {\bf h}_{2}) &= e[-\{{\bf h}_{2} \cdot {\bf t}_{g} + \boldeta_{1} (g, {\bf h}_{2}) \cdot ({\bf N}_{1}^{-1} {\bf m}_{1})\}]\cr &\quad \times Z\{S_{g}^{(1)} ({\bf m}_{1}), {\bf h}_{2}\}.}]

This formula allows the transposition of intermediate results Z from an indexing by[(\hbox{all } {\bf m}_{1}) \times (\hbox{unique } {\bf h}_{2})]to an indexing by[(\hbox{unique } {\bf m}_{1}) \times (\hbox{all } {\bf h}_{2}).]We may then apply the twiddle factors to obtain[Y^{*} ({\bf m}_{1}, {\bf h}_{2}) = e[-{\bf h}_{2} \cdot ({\bf N}^{-1} {\bf m}_{1})] Z ({\bf m}_{1}, {\bf h}_{2})]and carry out the second transform on [{\bf h}_{2}][Y({\bf m}_{1}, {\bf m}_{2}) = {\textstyle\sum\limits_{{\bf h}_{2} \in {\bb Z}^{3}/{\bf N}_{2}^{T} {\bb Z}^{3}}} Y^{*} ({\bf m}_{1}, {\bf h}_{2}) e[-{\bf h}_{2} \cdot ({\bf N}_{2}^{-1} {\bf m}_{2})].]The results, indexed by[(\hbox{unique } {\bf m}_{1}) \times (\hbox{all } {\bf m}_{2})]yield essentially an asymmetric unit of electron densities by the rearrangement[\rho\llap{$-\!$} ({\bf m}_{1} + {\bf N}_{1}{\bf m}_{2}) = Y({\bf m}_{1}, {\bf m}_{2}).]

The equivalence of the two transposition formulae up to the intervening twiddle factors is readily established, using the relation[{\bf h}_{2} \cdot [{\bf N}_{2}^{-1} {\boldmu}_{2} (g, {\bf m}_{1})] = \boldeta_{1} (g, {\bf h}_{2}) \cdot ({\bf N}_{1}^{-1} {\bf m}_{1}) \hbox{ mod } 1]which is itself a straightforward consequence of the identity[{\bf h} \cdot [{\bf N}^{-1} S_{g} ({\bf m})] = {\bf h} \cdot {\bf t}_{g} + ({\bf R}_{g}^{T}{\bf h}) \cdot ({\bf N}^{-1} {\bf m}).]

To complete the characterization of the effect of symmetry on the Cooley–Tukey factorization, and of the economy of computation it allows, it remains to consider the possibility that some values of [{\bf m}_{1}] may be invariant under some transformations [g \in G] under the action [{\bf m}_{1} \,\longmapsto\, S_{g}^{(1)} ({\bf m}_{1})].

Suppose that [{\bf m}_{1}] has a nontrivial isotropy subgroup [G_{{\bf m}_{1}}], and let [g \in G_{{\bf m}_{1}}]. Then each subarray [Y_{{\bf m}_{1}}] defined by[Y_{{\bf m}_{1}} ({\bf m}_{2}) = Y({\bf m}_{1}, {\bf m}_{2}) = \rho ({\bf m}_{1} + {\bf N}_{1}{\bf m}_{2})]satisfies the identity[\eqalign{ Y_{{\bf m}_{1}} ({\bf m}_{2}) &= Y_{S_{g}^{(1)} ({\bf m}_{1})} [S_{g}^{(2)} ({\bf m}_{2}) + {\boldmu}_{2} (g, {\bf m}_{1})]\cr &= Y_{{\bf m}_{1}} [S_{g}^{(2)} ({\bf m}_{2}) + {\boldmu}_{2} (g, {\bf m}_{1})]}]so that the data for the transform on [{\bf m}_{2}] have residual symmetry properties. In this case the identity satisfied by [\boldmu_{2}] simplifies to[{\boldmu}_{2}(gg', {\bf m}_{1}) = S_{g}^{(2)} [{\boldmu}_{2} (g', {\bf m}_{1})] + {\boldmu}_{2} (g, {\bf m}_{1}) \hbox{ mod } {\bf N}_{2} {\bb Z}^{3},]which shows that the mapping [g \,\longmapsto\, \boldmu_{2} (g, {\bf m}_{1})] satisfies the Frobenius congruences (Section 1.3.4.2.2.3[link]). Thus the internal symmetry of subarray [Y_{{\bf m}_{1}}] with respect to the action of G on [{\bf m}_{2}] is given by [G_{{\bf m}_{1}}] acting on [{\bb Z}^{3} / {\bf N}_{2} {\bb Z}^{3}] via[{\bf m}_{2} \,\longmapsto\, S_{g}^{(2)} ({\bf m}_{2}) + {\boldmu}_{2} (g, {\bf m}_{1}) \hbox{ mod } {\bf N}_{2} {\bb Z}^{3}.]

The transform on [{\bf m}_{2}] needs only be performed for one out of [[G:G_{{\bf m}_{1}}]] distinct arrays [Y_{{\bf m}_{1}}] (results for the others being obtainable by the transposition formula), and this transforms is [G_{{\bf m}_{1}}]-symmetric. In other words, the following cases occur:[\let\normalbaselines\relax\openup3pt\matrix{(\hbox{i})\hfill &G_{{\bf m}_{1}} = \{e\}\hfill & \hbox{maximum saving in computation}\hfill\cr & & (\hbox{by } |G|)\hbox{\semi}\hfill\cr &&{\bf m}_{2}\hbox{-transform has no symmetry}.\hfill\cr (\hbox{ii})\hfill & G_{{\bf m}_{1}} = G' \,\lt\, G\hfill &\hbox{saving in computation by a factor}\hfill\cr && \hbox{of } [G:G']\hbox{\semi}\hfill\cr && {\bf m}_{2}\hbox{-transform is } G'\hbox{-symmetric}.\hfill \cr (\hbox{iii})\hfill & G_{{\bf m}_{1}} = G \hfill & \hbox{no saving in computation}\hbox{\semi}\hfill\cr && {\bf m}_{2}\hbox{-transform is } G\hbox{-symmetric}.\hfill}]

The symmetry properties of the [{\bf m}_{2}]-transform may themselves be exploited in a similar way if [{\bf N}_{2}] can be factored as a product of smaller decimation matrices; otherwise, an appropriate symmetrized DFT routine may be provided, using for instance the idea of `multiplexing/demultiplexing' (Section 1.3.4.3.5[link]). We thus have a recursive descent procedure, in which the deeper stages of the recursion deal with transforms on fewer points, or of lower symmetry (usually both).

The same analysis applies to the [{\bf h}_{1}]-transforms on the sub­arrays [Z_{{\bf h}_{2}}^{*}], and leads to a similar descent procedure.

In conclusion, crystallographic symmetry can be fully exploited to reduce the amount of computation to the minimum required to obtain the unique results from the unique data. No such analysis was so far available in cases where the asymmetric units in real and reciprocal space are not parallelepipeds. An example of this procedure will be given in Section 1.3.4.3.6.5[link].

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.

1.3.4.3.4.3. Crystallographic extension of the Rader/Winograd factorization

| top | pdf |

As was the case in the absence of symmetry, the two previous classes of algorithms can only factor the global transform into partial transforms on prime numbers of points, but cannot break the latter down any further. Rader's idea of using the action of the group of units [U(p)] to obtain further factorization of a p-primary transform has been used in `scalar' form by Auslander & Shenefelt (1987)[link], Shenefelt (1988)[link] and Auslander et al. (1988)[link]. It will be shown here that it can be adapted to the crystallographic case so as to take advantage also of the possible existence of n-fold cyclic symmetry elements [(n = 3,\,4,\,6)] in a two-dimensional transform (Bricogne & Tolimieri, 1990[link]). This adaptation entails the use of certain rings of algebraic integers rather than ordinary integers, whose connection with the handling of cyclic symmetry will now be examined.

Let G be the group associated with a threefold axis of symmetry: [G = \{e, g, g^{2}\}] with [g^{3} = e]. In a standard trigonal basis, G has matrix representation[{\bf R}_{e} = \pmatrix{1 &0\cr 0 &1\cr} = {\bf I}, \quad {\bf R}_{g} = \pmatrix{0 &-1\cr 1 &-1\cr}, \quad {\bf R}_{g^{2}} = \pmatrix{-1 &1\cr -1 &0\cr}]in real space,[{\bf R}_{e}^{*} = \pmatrix{1 &0\cr 0 &1\cr} = {\bf I}, \quad {\bf R}_{g}^{*} = \pmatrix{-1 &-1\cr \,\,\,1 &\,\,\,0\cr}, \quad {\bf R}_{g^{2}}^{*} = \pmatrix{\,\,\,0 &\,\,\,1\cr -1 &-1\cr}]in reciprocal space. Note that[{\bf R}_{g^{2}}^{*} = [{\bf R}_{g^{2}}^{-1}]^{T} = {\bf R}_{g}^{T},]and that[{\bf R}_{g}^{T} = {\bf J}^{-1} {\bf R}_{g}{\bf J},\quad \hbox{ where } {\bf J} = \pmatrix{1 &\,\,\,0\cr 0 &-1\cr}]so that [{\bf R}_{g}] and [{\bf R}_{g}^{T}] are conjugate in the group of [2\times 2] unimodular integer matrices. The group ring [{\bb Z}G] is commutative, and has the structure of the polynomial ring [{\bb Z}[X]] with the single relation [X^{2} + X + 1 = 0] corresponding to the minimal polynomial of [{\bf R}_{g}]. In the terminology of Section 1.3.3.2.4[link], the ring structure of [{\bb Z}G] is obtained from that of [{\bb Z}[X]] by carrying out polynomial addition and multiplication modulo [X^{2} + X + 1], then replacing X by any generator of G. This type of construction forms the very basis of algebraic number theory [see Artin (1944[link], Section IIc) for an illustration of this viewpoint], and [{\bb Z}G] as just defined is isomorphic to the ring [{\bb Z}[\omega]] of algebraic integers of the form [a + b\omega\ [a, b\in {\bb Z},\omega = \exp (2\pi i/3)]] under the identification [X \leftrightarrow \omega]. Addition in this ring is defined component-wise, while multiplication is defined by[\eqalign{(a_{1} + b_{1} \omega) \times (a_{2} + b_{2} \omega) &= (a_{1} a_{2} - b_{1} b_{2}) \cr&\quad+{ [(a_{1} - b_{1}) b_{2} + b_{1} a_{2}] \omega.}\cr}]

In the case of a fourfold axis, [G = \{e, g, g^{2}, g^{3}\}] with [g^{4} = e], and[{\bf R}_{g} = \pmatrix{0 &-1\cr 1 &\,\,\,0\cr} = {\bf R}_{g}^{*}, \quad \hbox{with again } {\bf R}_{g}^{T} = {\bf J}^{-1} {\bf R}_{g}{\bf J}.][{\bb Z}G] is obtained from [{\bb Z}[X]] by carrying out polynomial arithmetic modulo [X^{2} + 1]. This identifies [{\bb Z}G] with the ring [{\bb Z}[i]] of Gaussian integers of the form [a + bi], in which addition takes place component-wise while multiplication is defined by[(a_{1} + b_{1} i) \times (a_{2} + b_{2} i) = (a_{1} a_{2} - b_{1} b_{2}) + (a_{1} b_{2} + b_{1} a_{2})i.]

In the case of a sixfold axis, [G = \{e, g, g^{2}, g^{3}, g^{4}, g^{5}\}] with [g^{6} = e], and[{\bf R}_{g} = \pmatrix{1 &-1\cr 1 &\,\,\,0\cr}, \quad {\bf R}_{g}^{*} = \pmatrix{0 &-1\cr 1 &\,\,\,1\cr}, \quad {\bf R}_{g}^{T} = {\bf J}^{-1} {\bf R}_{g}{\bf J}.][{\bb Z}G] is isomorphic to [{\bb Z}[\omega]] under the mapping [g \leftrightarrow 1 + \omega] since [(1 + \omega)^{6} = 1].

Thus in all cases [{\bb Z}G \cong {\bb Z}[X]/P(X)] where [P(X)] is an irreducible quadratic polynomial with integer coefficients.

The actions of G on lattices in real and reciprocal space (Sections 1.3.4.2.2.4[link], 1.3.4.2.2.5[link]) extend naturally to actions of [{\bb Z}G] on [{\bb Z}^{2}] in which an element [z = a + bg] of [{\bb Z}G] acts via[{\bf m} = \pmatrix{m_{1}\cr m_{2}\cr} \,\longmapsto\, z{\bf m} = (a{\bf I} + b{\bf R}_{g}) \pmatrix{{\bf m}_{1}\cr {\bf m}_{2}\cr}]in real space, and via[{\bf h} = \pmatrix{h_{1}\cr h_{2}\cr} \,\longmapsto\, z{\bf h} = (a{\bf I} + b{\bf R}_{g}^{T}) \pmatrix{h_{1}\cr h_{2}\cr}]in reciprocal space. These two actions are related by conjugation, since[(a{\bf I} + b{\bf R}_{g}^{T}) = {\bf J}^{-1} (a{\bf I} + b{\bf R}_{g}){\bf J}]and the following identity (which is fundamental in the sequel) holds:[(z{\bf h}) \cdot {\bf m} = {\bf h} \cdot (z{\bf m}) \quad \hbox{for all } {\bf m},{\bf h} \in {\bb Z}^{2}.]

Let us now consider the calculation of a [p \times p] two-dimensional DFT with n-fold cyclic symmetry [(n = 3,\,4,\,6)] for an odd prime [p \geq 5]. Denote [{\bb Z}/p {\bb Z}] by [{\bb Z}_{p}]. Both the data and the results of the DFT are indexed by [{\bb Z}_{p} \times {\bb Z}_{p}]: hence the action of [{\bb Z}G] on these indices is in fact an action of [{\bb Z}_{p}G], the latter being obtained from [{\bb Z}G] by carrying out all integer arithmetic in [{\bb Z}G] modulo p. The algebraic structure of [{\bb Z}_{p}G] combines the symmetry-carrying ring structure of [{\bb Z}G] with the finite field structure of [{\bb Z}_{p}] used in Section 1.3.3.2.3.1[link], and holds the key to a symmetry-adapted factorization of the DFT at hand.

The structure of [{\bb Z}_{p}G] depends on whether [P(X)] remains irreducible when considered as a polynomial over [{\bb Z}_{p}]. Thus two cases arise:

  • (1) [P(X)] remains irreducible mod p, i.e. there is no nth root of unity in [{\bb Z}_{p}];

  • (2) [P(X)] factors as [(X - u)(X - v)], i.e. there are nth roots of unity in [{\bb Z}_{p}].

These two cases require different developments.

  • Case 1. [{\bb Z}_{p}G] is a finite field with [p^{2}] elements. There is essentially (i.e. up to isomorphism) only one such field, denoted [GF(p^{2})], and its group of units is a cyclic group with [p^{2} - 1] elements. If γ is a generator of this group of units, the input data [\rho_{{\bf m}}] with [{\bf m} \ne {\bf 0}] may be reordered as[{\bf m}_{0}, \gamma {\bf m}_{0}, \gamma^{2} {\bf m}_{0}, \gamma^{3} {\bf m}_{0}, \ldots, \gamma^{p^{2}-2} {\bf m}_{0}]by the real-space action of γ; while the results [F_{\bf h}] with [{\bf h} \neq {\bf 0}] may be reordered as[{\bf h}_{0}, \gamma {\bf h}_{0}, \gamma^{2} {\bf h}_{0}, \gamma^{3} {\bf h}_{0}, \ldots, \gamma^{p^{2}-2} {\bf h}_{0}]by the reciprocal-space action of γ, where [{\bf m}_{0}] and [{\bf h}_{0}] are arbitrary nonzero indices.

    The core [{\bf C}_{p \times p}] of the DFT matrix, defined by[{\bf F}_{p \times p} = \pmatrix{1 &1 &\ldots &1\cr 1 & & &\cr \vdots & &{\bf C}_{p \times p} &\cr 1 & & &\cr},]will then have a skew-circulant structure (Section 1.3.3.2.3.1[link]) since[({\bf C}_{p \times p})_{jk} = e \left[{(\gamma\hskip 2pt^{j} {\bf h}_{0}) \cdot (\gamma^{k} {\bf m}_{0}) \over p}\right] = e \left[{{\bf h}_{0} \cdot (\gamma\hskip 2pt^{j + k} {\bf m}_{0}) \over p}\right]]depends only on [j + k]. Multiplication by [{\bf C}_{p \times p}] may then be turned into a cyclic convolution of length [p^{2} - 1], which may be factored by two DFTs (Section 1.3.3.2.3.1[link]) or by Winograd's techniques (Section 1.3.3.2.4[link]). The latter factorization is always favourable, as it is easily shown that [p^{2} - 1] is divisible by 24 for any odd prime [p \geq 5]. This procedure is applicable even if no symmetry is present in the data.

    Assume now that cyclic symmetry of order [n = 3], 4 or 6 is present. Since n divides 24 hence divides [p^{2} - 1], the generator g of this symmetry is representable as [\gamma^{(p^{2} - 1)/n}] for a suitable generator γ of the group of units. The reordered data will then be [(p^{2} - 1)/n]-periodic rather than simply [(p^{2} - 1)]-periodic; hence the reindexed results will be n-decimated (Section 1.3.2.7.2[link]), and the [(p^{2} - 1)/n] nonzero results can be calculated by applying the DFT to the [(p^{2} - 1)/n] unique input data. In this way, the n-fold symmetry can be used in full to calculate the core contributions from the unique data to the unique results by a DFT of length [(p^{2} - 1)/n].

    It is a simple matter to incorporate nonprimitive translations into this scheme. For example, when going from structure factors to electron densities, reordered data items separated by [(p^{2} - 1)/n] are not equal but differ by a phase shift proportional to their index mod p, whose effect is simply to shift the origin of the n-decimated transformed sequence. The same economy of computation can therefore be achieved as in the purely cyclic case.

    Dihedral symmetry elements, which map g to [g^{-1}] (Section 1.3.4.2.2.3[link]), induce extra one-dimensional symmetries of order 2 in the reordered data which can also be fully exploited to reduce computation.

  • Case 2. If [p \geq 5], it can be shown that the two roots u and v are always distinct. Then, by the Chinese remainder theorem (CRT) for polynomials (Section 1.3.3.2.4[link]) we have a ring isomorphism[{\bb Z}_{p} [X] / P(X) \cong \{{\bb Z}_{p} [X] / (X - u)\} \times \{{\bb Z}_{p} [X] / (X - v)\}]defined by sending a polynomial [Q(X)] from the left-hand-side ring to its two residue classes modulo [X - u] and [X - v], respectively. Since the latter are simply the constants [Q(u)] and [Q(v)], the CRT reindexing has the particularly simple form[a + bX \,\longmapsto\, (a + bu, a + bv) = (\alpha, \beta)]or equivalently[\pmatrix{a\cr b\cr} \,\longmapsto\, \pmatrix{\alpha\cr \beta\cr} = {\bf M} \pmatrix{a\cr b\cr} \hbox{mod } p, \quad \hbox{with } {\bf M} = \pmatrix{1 &u\cr 1 &v\cr}.]The CRT reconstruction formula similarly simplifies to[\displaylines{\pmatrix{\alpha\cr \beta\cr} \,\longmapsto\, \pmatrix{a\cr b\cr} = {\bf M}^{-1} \pmatrix{\alpha\cr \beta\cr} \hbox{mod } p,\cr \hbox{with } {\bf M}^{-1} = {1 \over v - u} \pmatrix{v &-u\cr -1 &1\cr}.}]The use of the CRT therefore amounts to the simultaneous diagonalization (by M) of all the matrices representing the elements of [{\bb Z}_{p}G] in the basis (1, X).

    A first consequence of this diagonalization is that the internal structure of [{\bb Z}_{p}G] becomes clearly visible. Indeed, [{\bb Z}_{p}G] is mapped isomorphically to a direct product of two copies of [{\bb Z}_{p}], in which arithmetic is carried out component-wise between eigenvalues α and β. Thus if[\eqalign{z &= a + bX {\buildrel {\scriptstyle {\rm CRT}} \over {\longleftrightarrow}} (\alpha, \beta),\cr z' &= a' + b' X {\buildrel {\scriptstyle {\rm CRT}} \over {\longleftrightarrow}} (\alpha', \beta'),}]then[\eqalign{z + z' &{\buildrel{\scriptstyle {\rm CRT}} \over {\longleftrightarrow}} (\alpha + \alpha', \beta + \beta'),\cr zz' &{\buildrel{\scriptstyle {\rm CRT}} \over {\longleftrightarrow}} (\alpha \alpha', \beta \beta').}]Taking in particular[\eqalign{z &{\buildrel{\scriptstyle {\rm CRT}} \over {\longleftrightarrow}} (\alpha, 0) \neq (0, 0),\cr z' &{\buildrel {\scriptstyle {\rm CRT}} \over {\longleftrightarrow}} (0, \beta) \neq (0, 0),}]we have [zz' = 0], so that [{\bb Z}_{p}G] contains zero divisors; therefore [{\bb Z}_{p}G] is not a field. On the other hand, if [z {\buildrel {\rm CRT} \over {\longleftrightarrow}} (\alpha, \beta)] with [\alpha \neq 0] and [\beta \neq 0], then α and β belong to the group of units [U(p)] (Section 1.3.3.2.3.1[link]) and hence have inverses [\alpha^{-1}] and [\beta^{-1}]; it follows that z is a unit in [{\bb Z}_{p}G], with inverse [{z}^{-1} {\buildrel {\rm CRT} \over {\longleftrightarrow}} (\alpha^{-1}, \beta^{-1})]. Therefore, [{\bb Z}_{p}G] consists of four distinct pieces:[\eqalign{0 &{\buildrel{\scriptstyle {\rm CRT}} \over {\longleftrightarrow}} \{(0, 0)\},\cr D_{1} &{\buildrel{\scriptstyle {\rm CRT}} \over {\longleftrightarrow}} \{(\alpha, 0) | \alpha \in U (p)\} \cong U (p),\cr D_{2} &{\buildrel{\scriptstyle {\rm CRT}}\over {\longleftrightarrow}} \{(0, \beta) | \beta \in U (p)\} \cong U (p),\cr U &{\buildrel{\scriptstyle {\rm CRT}}\over {\longleftrightarrow}} \{(\alpha, \beta) |\alpha \in U (p), \beta \in U (p)\} \cong U (p) \times U (p).}]

    A second consequence of this diagonalization is that the actions of [{\bb Z}_{p}G] on indices m and h can themselves be brought to diagonal form by basis changes:[\displaylines{\hfill {\bf m} \,\longmapsto\, (a {\bf I} + b {\bf R}_{g}) {\bf m}\hfill\cr \hfill \hbox{becomes } {\boldmu} \,\longmapsto\, \pmatrix{\alpha &0\cr 0 &\beta\cr} {\boldmu} \quad \hbox{with } {\boldmu} = {\bf Mm},\hfill\cr \hfill {\bf h} \,\longmapsto\, (a {\bf I} + b {\bf R}_{g}^{T}) {\bf h}\hfill\cr \hbox{becomes}\, \boldeta \,\longmapsto\, \pmatrix{\alpha &0\cr 0 &\beta\cr} \boldeta \quad \hbox{with } \boldeta = {\bf MJh.}}]Thus the sets of indices μ and η can be split into four pieces as [{\bb Z}_{p}G] itself, according as these indices have none, one or two of their coordinates in [U(p)]. These pieces will be labelled by the same symbols – 0, [D_{1}], [D_{2}] and U – as those of [{\bb Z}_{p}G].

    The scalar product [{\bf h} \cdot {\bf m}] may be written in terms of η and μ as[{\bf h} \cdot {\bf m} = [\boldeta \cdot (({\bf M}^{-1})^{T} {\bf JM}^{-1}) {\boldmu}],]and an elementary calculation shows that the matrix [\boldDelta = ({\bf M}^{-1})^{T} {\bf JM}^{-1}] is diagonal by virtue of the relation[uv = \hbox{constant term in } P(X) = 1.]Therefore, [{\bf h} \cdot {\bf m} = 0] if [{\bf h} \in D_{1}] and [{\boldmu} \in D_{2}] or vice versa.

    We are now in a position to rearrange the DFT matrix [{\bf F}_{p \times p}]. Clearly, the structure of [{\bf F}_{p \times p}] is more complex than in case 1, as there are three types of `core' matrices:[\eqalign{\hbox{type 1:} \quad &D \times D\ (\hbox {with } D = D_{1} \hbox{ or } D_{2})\hbox{\semi}\cr \hbox{type 2:} \quad &D \times U \hbox{ or } U \times D\hbox{\semi}\cr \hbox{type 3:} \quad &U \times U.}](Submatrices of type [D_{1} \times D_{2}] and [D_{2} \times D_{1}] have all their elements equal to 1 by the previous remark.)

    Let γ be a generator of [U(p)]. We may reorder the elements in [D_{1}], [D_{2}] and U – and hence the data and results indexed by these elements – according to powers of γ. This requires one exponent in each of [D_{1}] and [D_{2}], and two exponents in U. For instance, in the h-index space:[\eqalign{D_{1} &= \left\{\pmatrix{\gamma &0\cr 0 &0\cr}^{j} \pmatrix{\eta_{1}\cr 0\cr}_{0} \Big|\, j = 1, \ldots, p - 1\right\}\cr D_{2} &= \left\{\pmatrix{0 &0\cr 0 &\gamma\cr}^{j} \pmatrix{0\cr \eta_{2}\cr}_{0} \Big|\, j = 1, \ldots, p - 1\right\}\cr U &= \left\{\pmatrix{\gamma &0\cr 0 &1\cr}^{j_{1}} \pmatrix{1 &0\cr 0 &\gamma\cr}^{j_{2}} \pmatrix{\eta_{1}\cr \eta_{2}\cr}_{0} \Big|\,j_{1} = 1, \ldots, p - 1\hbox{\semi}\right.\cr &\left. {\hbox to 137pt{}}j_{2} = 1, \ldots, p - 1\right.\biggr\}}]and similarly for the μ index.

    Since the diagonal matrix Δ commutes with all the matrices representing the action of γ, this rearrangement will induce skew-circulant structures in all the core matrices. The corresponding cyclic convolutions may be carried out by Rader's method, i.e. by diagonalizing them by means of two ([p - 1])-point one-dimensional DFTs in the [D \times D] pieces and of two [(p - 1) \times (p - 1)]-point two-dimensional DFTs in the [U \times U] piece (the [U \times D] and [D \times U] pieces involve extra section and projection operations).

    In the absence of symmetry, no computational saving is achieved, since the same reordering could have been applied to the initial [{\bb Z}_{p} \times {\bb Z}_{p}] indexing, without the CRT reindexing.

    In the presence of n-fold cyclic symmetry, however, the rearranged [{\bf F}_{p \times p}] lends itself to an n-fold reduction in size. The basic fact is that whenever case 2[link] occurs, [p - 1] is divisible by n (i.e. [p - 1] is divisible by 6 when [n = 3] or 6, and by 4 when [n = 4]), say [p - 1 = nq]. If g is a generator of the cyclic symmetry, the generator γ of [U(p)] may be chosen in such a way that [g = \gamma^{q}]. The action of g is then to increment the j index in [D_{1}] and [D_{2}] by q, and the [(j_{1}, j_{2})] index in U by (q, q). Since the data items whose indices are related in this way have identical values, the DFTs used to diagonalize the Rader cyclic convolutions will operate on periodized data, hence yield decimated results; and the nonzero results will be obtained from the unique data by DFTs n times smaller than their counterparts in the absence of symmetry.

    A more thorough analysis is needed to obtain a Winograd factorization into the normal from CBA in the presence of symmetry (see Bricogne & Tolimieri, 1990[link]).

    Nonprimitive translations and dihedral symmetry may also be accommodated within this framework, as in case 1[link].

    This reindexing by means of algebraic integers yields larger orbits, hence more efficient algorithms, than that of Auslander et al. (1988)[link] which only uses ordinary integers acting by scalar dilation.

References

Artin, E. (1944). Galois Theory. Notre Dame University Press.
Auslander, L., Johnson, R. W. & Vulis, M. (1988). Evaluating finite Fourier transforms that respect group symmetries. Acta Cryst. A44, 467–478.
Auslander, L. & Shenefelt, M. (1987). Fourier transforms that respect crystallographic symmetries. IBM J. Res. Dev. 31, 213–223.
Bricogne, G. & Tolimieri, R. (1990). Two-dimensional FFT algorithms on data admitting 90°-rotational symmetry. In Signal Processing Theory, edited by L. Auslander, T. Kailath & S. Mitter, pp. 25–35. New York: Springer-Verlag.
Curtis, C. W. & Reiner, I. (1962). Representation Theory of Finite Groups and Associative Algebras. New York: Wiley–Interscience.
Hall, M. (1959). The Theory of Groups. New York: Macmillan.
MacLane, S. (1963). Homology. Berlin: Springer-Verlag.
Shenefelt, M. (1988). Group Invariant Finite Fourier Transforms. PhD thesis, Graduate Centre of the City University of New York.








































to end of page
to top of page