Fast computation of multidimensional DFT

It is well known that multidimensional discrete Fourier transforms (DFT) can be performed via one-dimensional DFT's. The paper builds up on the following result of \textit{I. Gertner} [IEEE Trans. Acoust. Speech Signal Process. ASSP-36, No. 7, 1036-1050 (1988; Zbl 0658.65146)]: The number \(m(N,d)\) of one-dimensional DFT's of length \(N\) which is necessary to realize a \(d\)-dimensional DFT of size \(N^ d\) is equal to the number of lines through the origin with coefficients in \(\mathbb{Z}/N\mathbb{Z}\) and with the property that every of the \(N^ d\) points lies at least on one line. Discussing the congruence \(ax-bt\equiv 0\) (\({}\bmod N)\) (\(a,b,x\in (Z/NZ)^ d\)) the authors show that \(m(N,d)=N^{(d-1)}\prod^ s_{i=1}(1+p_ i^{-1}+\dots +p_ i^{-d+1})\), where the \(p_ i\) (\(i=1,\dots,s)\) are the different prime factors of \(N\).

Recommendations

Cited in

(9)

This page was built for publication: Fast computation of multidimensional DFT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1177501)