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

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. Bricognea

aMRC 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 , using the cyclic structure of the multiplicative group of units . The latter consists of all those elements of which are not divisible by p, and thus has elements. It is cyclic, and there exist primitive roots g modulo such that The elements divisible by p, which are divisors of zero, have to be treated separately just as 0 had to be treated separately for .

When , then with . The results are p-decimated, hence can be obtained via the -point DFT of the -periodized data Y: with When , then we may write where contains the contributions from and those from . By a converse of the previous calculation, arises from p-decimated data Z, hence is the -periodization of the -point DFT of these data: with (the -periodicity follows implicity from the fact that the transform on the right-hand side is independent of ).

Finally, the contribution from all may be calculated by reindexing by the powers of a primitive root g modulo , i.e. by writing then carrying out the multiplication by the skew-circulant matrix core as a convolution.

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

References

Winograd, S. (1976). On computing the discrete Fourier transform. Proc. Natl Acad. Sci. USA, 73, 1005–1006.
Winograd, S. (1978). On computing the discrete Fourier transform. Math. Comput. 32, 175–199.