Factorization method for crystallographic Fourier transforms (Q919792)

Let p,q be primes (p\(\neq q)\) and \(n=pq\). Algorithms for computing the 3- dimensional discrete Fourier transform (DFT) of size \(n\times n\times n\) that take advantage of crystal symmetries are developed. The symmetry of a crystal gives rise to redundancy in the sampled data, i.e., the data are invariant under a space group G of the crystal. The DFT of G- invariant data without redundant arithmetic is called a symmetrized DFT. The main result is the orbit exchange. This is a procedure for designing symmetrized DFT-algorithms of size \(n\times n\times n\) which reduce to symmetrized DFT's on the prime factors of n. Note that fast algorithms for symmetrized DFT of prime size are known.