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 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 component-wise 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.

#### 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 . Then any grid point index in real space may be writtenwith and determined byThese relations establish a one-to-one 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 G-invariant 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 G-modules 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 electron-density 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 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 ) 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 sub­arrays , 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.

#### 1.3.4.3.4.2. Multidimensional Good factorization

| top | pdf |

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 p-primary 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 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.

| 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 to obtain further factorization of a p-primary 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 n-fold cyclic symmetry elements in a two-dimensional 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 component-wise, 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 component-wise 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 two-dimensional DFT with n-fold 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 symmetry-carrying ring structure of with the finite field structure of used in Section 1.3.3.2.3.1, and holds the key to a symmetry-adapted factorization of the DFT at hand.

The structure of depends on whether remains irreducible when considered as a polynomial over . Thus two cases arise:

 (1) remains irreducible mod p, i.e. there is no nth root of unity in ; (2) factors as , i.e. there are nth roots of unity in .

These two cases require different developments.

 Case 1. is a finite field with elements. There is essentially (i.e. up to isomorphism) only one such field, denoted , and its group of units is a cyclic group with elements. If γ is a generator of this group of units, the input data with may be reordered asby the real-space action of γ; while the results with may be reordered asby the reciprocal-space action of γ, where and are arbitrary nonzero indices. The core of the DFT matrix, defined bywill then have a skew-circulant structure (Section 1.3.3.2.3.1) sincedepends only on . Multiplication by may then be turned into a cyclic convolution of length , which may be factored by two DFTs (Section 1.3.3.2.3.1) or by Winograd's techniques (Section 1.3.3.2.4). The latter factorization is always favourable, as it is easily shown that is divisible by 24 for any odd prime . This procedure is applicable even if no symmetry is present in the data. Assume now that cyclic symmetry of order , 4 or 6 is present. Since n divides 24 hence divides , the generator g of this symmetry is representable as for a suitable generator γ of the group of units. The reordered data will then be -periodic rather than simply -periodic; hence the reindexed results will be n-decimated (Section 1.3.2.7.2), and the nonzero results can be calculated by applying the DFT to the 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 . 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 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 (Section 1.3.4.2.2.3), induce extra one-dimensional symmetries of order 2 in the reordered data which can also be fully exploited to reduce computation. Case 2. If , 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) we have a ring isomorphismdefined by sending a polynomial from the left-hand-side ring to its two residue classes modulo and , respectively. Since the latter are simply the constants and , the CRT reindexing has the particularly simple formor equivalentlyThe CRT reconstruction formula similarly simplifies toThe use of the CRT therefore amounts to the simultaneous diagonalization (by M) of all the matrices representing the elements of in the basis (1, X). A first consequence of this diagonalization is that the internal structure of becomes clearly visible. Indeed, is mapped isomorphically to a direct product of two copies of , in which arithmetic is carried out component-wise between eigenvalues α and β. Thus ifthenTaking in particularwe have , so that contains zero divisors; therefore is not a field. On the other hand, if with and , then α and β belong to the group of units (Section 1.3.3.2.3.1) and hence have inverses and ; it follows that z is a unit in , with inverse . Therefore, consists of four distinct pieces: A second consequence of this diagonalization is that the actions of on indices m and h can themselves be brought to diagonal form by basis changes:Thus the sets of indices μ and η can be split into four pieces as itself, according as these indices have none, one or two of their coordinates in . These pieces will be labelled by the same symbols – 0, , and U – as those of . The scalar product may be written in terms of η and μ asand an elementary calculation shows that the matrix is diagonal by virtue of the relationTherefore, if and or vice versa. We are now in a position to rearrange the DFT matrix . Clearly, the structure of is more complex than in case 1, as there are three types of `core' matrices:(Submatrices of type and have all their elements equal to 1 by the previous remark.) Let γ be a generator of . We may reorder the elements in , and U – and hence the data and results indexed by these elements – according to powers of γ. This requires one exponent in each of and , and two exponents in U. For instance, in the h-index space: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 ()-point one-dimensional DFTs in the pieces and of two -point two-dimensional DFTs in the piece (the and 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 indexing, without the CRT reindexing. In the presence of n-fold cyclic symmetry, however, the rearranged lends itself to an n-fold reduction in size. The basic fact is that whenever case 2 occurs, is divisible by n (i.e. is divisible by 6 when or 6, and by 4 when ), say . If g is a generator of the cyclic symmetry, the generator γ of may be chosen in such a way that . The action of g is then to increment the j index in and by q, and the 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). Nonprimitive translations and dihedral symmetry may also be accommodated within this framework, as in case 1. This reindexing by means of algebraic integers yields larger orbits, hence more efficient algorithms, than that of Auslander et al. (1988) 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.