N
                 a power of an odd prime

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, p. 53 | 1 | 2 |

Section 1.3.3.2.3.2. N a power of an odd prime

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.3.2.3.2. N a power of an odd prime

| top | pdf |

This idea was extended by Winograd (1976, 1978) to the treatment of prime powers $[N = p^{\nu}]$ , using the cyclic structure of the multiplicative group of units $[U(p^{\nu})]$ . The latter consists of all those elements of $[{\bb Z} / p^{\nu} {\bb Z}]$ which are not divisible by p, and thus has $[q_{\nu} = p^{\nu - 1} (p - 1)]$ elements. It is cyclic, and there exist primitive roots g modulo $[p^{\nu}]$ such that $[U(p^{\nu}) = \{1, g, g^{2}, g^{3}, \ldots, g^{q_{\nu} - 1}\}.]$ The $[p^{\nu - 1}]$ elements divisible by p, which are divisors of zero, have to be treated separately just as 0 had to be treated separately for [N = p] .

When $[k^{*} \not\in U(p^{\nu})]$ , then $[k^{*} = pk_{1}^{*}]$ with $[k_{1}^{*} \in {\bb Z} / p^{\nu - 1} {\bb Z}]$ . The results $[X^{*} (pk_{1}^{*})]$ are p-decimated, hence can be obtained via the $[p^{\nu - 1}]$ -point DFT of the $[p^{\nu - 1}]$ -periodized data Y: $[X^{*} (pk_{1}^{*}) = \bar{F} (p^{\nu - 1}) [{\bf Y}] (k_{1}^{*})]$ with $[Y(k_{1}) = {\textstyle\sum\limits_{k_{2} \in {\bb Z} / p {\bb Z}}} X(k_{1} + p^{\nu - 1} k_{2}).]$

When $[k^{*} \in U(p^{\nu})]$ , then we may write $[X^{*} (k^{*}) = X_{0}^{*} (k^{*}) + X_{1}^{*} (k^{*}),]$ where $[{\bf X}_{0}^{*}]$ contains the contributions from $[k\; \notin\; U(p^{\nu})]$ and $[{\bf X}_{1}^{*}]$ those from $[k \in U(p^{\nu})]$ . By a converse of the previous calculation, $[{\bf X}_{0}^{*}]$ arises from p-decimated data Z, hence is the $[p^{\nu - 1}]$ -periodization of the $[p^{\nu - 1}]$ -point DFT of these data: $[X_{0}^{*} (p^{\nu - 1} k_{1}^{*} + k_{2}^{*}) = \bar{F} (p^{\nu - 1}) [{\bf Z}] (k_{2}^{*})]$ with $[Z(k_{2}) = X(pk_{2}), \qquad k_{2} \in {\bb Z} / p^{\nu - 1} {\bb Z}]$ (the $[p^{\nu - 1}]$ -periodicity follows implicity from the fact that the transform on the right-hand side is independent of $[k_{1}^{*} \in {\bb Z} / p {\bb Z}]$ ).

Finally, the contribution $[X_{1}^{*}]$ from all $[k \in U(p^{\nu})]$ may be calculated by reindexing by the powers of a primitive root g modulo $[p^{\nu}]$ , i.e. by writing $[X_{1}^{*} (g^{m^{*}}) = {\textstyle\sum\limits_{m = 0}^{q_{\nu} - 1}} X(g^{m}) e(g^{(m^{*} + m) / p^{\nu}})]$ then carrying out the multiplication by the skew-circulant matrix core as a convolution.

Thus the DFT of size $[p^{\nu}]$ may be reduced to two DFTs of size $[p^{\nu - 1}]$ (dealing, respectively, with p-decimated results and p-decimated data) and a convolution of size $[q_{\nu} = p^{\nu - 1} (p - 1)]$ . The latter may be `diagonalized' into a multiplication by purely real or purely imaginary numbers (because $[g^{(q_{\nu} / 2)} = -1]$ ) by two DFTs, whose factoring in turn leads to DFTs of size $[p^{\nu - 1}]$ and [p - 1] . This method, applied recursively, allows the complete decomposition of the DFT on $[p^{\nu}]$ points into arbitrarily small DFTs.

References

Winograd, S. (1976). On computing the discrete Fourier transform. Proc. Natl Acad. Sci. USA, 73, 1005–1006.Google Scholar

Winograd, S. (1978). On computing the discrete Fourier transform. Math. Comput. 32, 175–199.Google Scholar

International Tables for Crystallography (2006). Vol. B. ch. 1.3, p. 53