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

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

G. Bricognea

aMRC Laboratory of Molecular Biology, Hills Road, Cambridge CB2 2QH, England, and LURE, Bâtiment 209D, Université Paris-Sud, 91405 Orsay, France

| 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 representation in real space, in reciprocal space. Note that and that so 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 via in real space, and via in reciprocal space. These two actions are related by conjugation, since and 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 as by the real-space action of γ; while the results with may be reordered as by the reciprocal-space action of γ, where and are arbitrary non-zero indices. The core of the DFT matrix, defined by will then have a skew-circulant structure (Section 1.3.3.2.3.1) since depends 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 non-zero 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 non-primitive 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 isomorphism defined 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 form or equivalently The CRT reconstruction formula similarly simplifies to The 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 if then Taking in particular we 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 μ as and an elementary calculation shows that the matrix is diagonal by virtue of the relation Therefore, 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 non-zero 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). Non-primitive 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.Google Scholar
Auslander, L., Johnson, R. W. & Vulis, M. (1988). Evaluating finite Fourier transforms that respect group symmetries. Acta Cryst. A44, 467–478.Google Scholar
Auslander, L. & Shenefelt, M. (1987). Fourier transforms that respect crystallographic symmetries. IBM J. Res. Dev. 31, 213–223.Google Scholar
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.Google Scholar
Shenefelt, M. (1988). Group invariant finite Fourier transforms. PhD thesis, Graduate Centre of the City University of New York.Google Scholar