Index transforms for multidimensional DFT's and convolutions (Q1119008): Difference between revisions

The computation of m-dimensional ``long'' discrete Fourier transforms (DFT's) convolutions can be transferred by so-called index transforms to the parallel computation of n-dimensional ``short'' DFT's convolutions \((n>m)\). It is shown that every index transform for DFT's convolutions is an isomorphism between the corresponding sets of indexes considered as finite abelian groups. This solves open problems posed by \textit{J. Hekrdla} [ibid. 51, 469-480 (1987; Zbl 0628.65144)]. Further, the results are used to extend the known Chinese remainder theorem to the multivariate case and to deduce new index transforms which allow a simplified implementation of input and output data permutations for fast DFT's.