Crystallographic extension of the Rader/Winograd 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. 76-79 | 1 | 2 |

Section 1.3.4.3.4.3. Crystallographic extension of the Rader/Winograd 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.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), 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 $[(n = 3,\;4,\;6)]$ 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: $[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, 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, 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, 1.3.4.2.2.5) 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, 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) remains irreducible mod p, i.e. there is no nth root of unity in $[{\bb Z}_{p}]$ ;
(2) factors as , 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 non-zero 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) 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 . 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) or by Winograd's techniques (Section 1.3.3.2.4). 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 , 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), and the $[(p^{2} - 1)/n]$ non-zero 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 non-primitive 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), 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) 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 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 $[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 , 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 (Section 1.3.3.2.3.1) 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 . 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{;}\cr \hbox{type 2:} \quad &D \times U \hbox{ or } U \times D\hbox{;}\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 . 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{;}\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 ()-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 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 $[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 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

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