Author: Hans Munthe-Kaas

TechRep: Department of Math. Sciences, NTNU Trondheim, May 1989.

Abstract: We examine the FFT of functions u : Rn → C, where u is both periodic in all variables and in addition possess certain symmetries. It is shown that all such functions allow symmetric FFT’s, where all the symmetries are used to obtain computational savings. These symmetric FFT’s includes the previously known symmetric transforms that are currently used in fast Poisson solvers. In addition new symmetries appear. These can e.g. be used in the construction of fast Poisson

solvers over certain 2–dimensional triangular domains. The triangular Poisson solvers have obvious applications in domain decomposition methods. The paper also contains a general description of nonsymmetric multidimensional FFT’s. This formalism may be useful for choosing multidimensional FFT algorithms for implementation on parallel computers.

Remarks in hindsight: I should have published this paper! I still like it many years later. I got  a negative referee report, and was put off trying to publish. A relevant critic was that the reference list is not complete. There exists similar work before this that I was not aware of at the time. A classic reference is:

L. F. Ten Eyck, Crystallographic fast Fourier transforms, Acta Cryst. (1973). A29, 183-191    [ doi:10.1107/S0567739473000458 ].