International
Tables for Crystallography Volume B Reciprocal space Edited by U. Shmueli © International Union of Crystallography 2010 
International Tables for Crystallography (2010). Vol. B, ch. 1.3, pp. 7985

Methods for factoring the DFT in the absence of symmetry were examined in Sections 1.3.3.2 and 1.3.3.3. 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 and are finite Abelian groups under componentwise addition. If an iterated addition is viewed as an action of an integer scalar viathen an Abelian group becomes a module over the ring (or, for short, a 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 bycan be combined with this action as follows:This provides a left action, on the indexing sets, of the setof symbolic linear combinations of elements of G with integral coefficients. If addition and multiplication are defined in byandwiththen is a ring, and the action defined above makes the indexing sets into modules. The ring is called the integral group ring of G (Curtis & Reiner, 1962, 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 submodules of the main modules.
Suppose, as in Section 1.3.3.3.2.1, that the decimation matrix N may be factored as . Then any grid point index in real space may be writtenwith and determined byThese relations establish a onetoone correspondence between and the Cartesian product of and , and hence as a set. However as an Abelian group, since in general because there can be a `carry' from the addition of the first components into the second components; therefore, as a module, which shows that the incorporation of symmetry into the Cooley–Tukey algorithm is not a trivial matter.
Let act on I throughand suppose that N `integerizes' all the nonprimitive translations so that we may writewith and determined as above. Suppose further that N, and commute with for all , i.e. (by Schur's lemma, Section 1.3.4.2.2.4) that these matrices are integer multiples of the identity in each Ginvariant subspace. The action of g on leads towhich we may decompose aswithand
Introducing the notationthe two components of may be writtenwith
The term is the geometric equivalent of a carry or borrow: it arises because , calculated as a vector in , may be outside the unit cell , and may need to be brought back into it by a `large' translation with a nonzero component in the space; equivalently, the action of g may need to be applied around different permissible origins for different values of , 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 as the cocycle of the extension of Gmodules described by the exact sequence .]
Thus G acts on I in a rather complicated fashion: although does define a left action in alone, no action can be defined in alone because depends on . However, because , and are left actions, it follows that satisfies the identityfor all g, in G and all in . In particular, for all , and
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 tofor all but only for the unique under the action of G in . Except in special cases which will be examined later, these vectors contain essentially an asymmetric unit of electrondensity data, up to some redundancies on boundaries. We may then compute the partial transform on :Using the symmetry of in the form yields by the procedure of Section 1.3.3.3.2 the transposition formula
By means of this identity we can transpose intermediate results initially indexed byso as to have them indexed byWe may then apply twiddle factors to getand carry out the second transformThe final results are indexed bywhich yield essentially an asymmetric unit of structure factors after unscrambling by:
The transposition formula above applies to intermediate results when going backwards from F to , provided these results are considered after the twiddlefactor 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 ) in a manner similar to that used for m.
LetwithWe may then writewithHere and are defined byand
Let us then form an array according tofor all but only for the unique under the action of G in , and transform on to obtainPutting and using the symmetry of F in the formwhereyields by a straightforward rearrangement
This formula allows the transposition of intermediate results Z from an indexing byto an indexing byWe may then apply the twiddle factors to obtainand carry out the second transform on The results, indexed byyield essentially an asymmetric unit of electron densities by the rearrangement
The equivalence of the two transposition formulae up to the intervening twiddle factors is readily established, using the relationwhich is itself a straightforward consequence of the identity
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 may be invariant under some transformations under the action .
Suppose that has a nontrivial isotropy subgroup , and let . Then each subarray defined bysatisfies the identityso that the data for the transform on have residual symmetry properties. In this case the identity satisfied by simplifies towhich shows that the mapping satisfies the Frobenius congruences (Section 1.3.4.2.2.3). Thus the internal symmetry of subarray with respect to the action of G on is given by acting on via
The transform on needs only be performed for one out of distinct arrays (results for the others being obtainable by the transposition formula), and this transforms is symmetric. In other words, the following cases occur:
The symmetry properties of the transform may themselves be exploited in a similar way if 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 transforms on the subarrays , 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.
This procedure was described in Section 1.3.3.3.2.2. The main difference with the Cooley–Tukey factorization is that if , where the different factors are pairwise coprime, then the Chinese remainder theorem reindexing makes isomorphic to a direct sum.where each pprimary piece is endowed with an induced 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, 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 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 pprimary 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 pprimary 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.
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 to obtain further factorization of a pprimary transform has been used in `scalar' form by Auslander & Shenefelt (1987), Shenefelt (1988) and Auslander et al. (1988). 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 nfold cyclic symmetry elements in a twodimensional transform (Bricogne & Tolimieri, 1990). 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: with . In a standard trigonal basis, G has matrix representationin real space,in reciprocal space. Note thatand thatso that and are conjugate in the group of unimodular integer matrices. The group ring is commutative, and has the structure of the polynomial ring with the single relation corresponding to the minimal polynomial of . In the terminology of Section 1.3.3.2.4, the ring structure of is obtained from that of by carrying out polynomial addition and multiplication modulo , then replacing X by any generator of G. This type of construction forms the very basis of algebraic number theory [see Artin (1944, Section IIc) for an illustration of this viewpoint], and as just defined is isomorphic to the ring of algebraic integers of the form under the identification . Addition in this ring is defined componentwise, while multiplication is defined by
In the case of a fourfold axis, with , and is obtained from by carrying out polynomial arithmetic modulo . This identifies with the ring of Gaussian integers of the form , in which addition takes place componentwise while multiplication is defined by
In the case of a sixfold axis, with , and is isomorphic to under the mapping since .
Thus in all cases where 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, 1.3.4.2.2.5) extend naturally to actions of on in which an element of acts viain real space, and viain reciprocal space. These two actions are related by conjugation, sinceand the following identity (which is fundamental in the sequel) holds:
Let us now consider the calculation of a twodimensional DFT with nfold cyclic symmetry for an odd prime . Denote by . Both the data and the results of the DFT are indexed by : hence the action of on these indices is in fact an action of , the latter being obtained from by carrying out all integer arithmetic in modulo p. The algebraic structure of combines the symmetrycarrying ring structure of with the finite field structure of used in Section 1.3.3.2.3.1, and holds the key to a symmetryadapted factorization of the DFT at hand.
The structure of depends on whether remains irreducible when considered as a polynomial over . Thus two cases arise:
These two cases require different developments.
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). Twodimensional 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: SpringerVerlag.
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: SpringerVerlag.
Shenefelt, M. (1988). Group Invariant Finite Fourier Transforms. PhD thesis, Graduate Centre of the City University of New York.