Multidimensional Cooley–Tukey factorization

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. 74-76 | 1 | 2 |

Section 1.3.4.3.4.1. Multidimensional Cooley–Tukey factorization

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.4.1. Multidimensional Cooley–Tukey factorization

| top | pdf |

Suppose, as in Section 1.3.3.3.2.1, 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 non-primitive 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) 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 non-zero 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; MacLane, 1963) 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. 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 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 non-trivial 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). 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{;}\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{;}\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{;}\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). 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 subarrays $[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.

References

Hall, M. (1959). The theory of groups. New York: Macmillan.Google Scholar

MacLane, S. (1963). Homology. Berlin: Springer-Verlag.Google Scholar

International Tables for Crystallography (2006). Vol. B. ch. 1.3, pp. 74-76