Given a $z\in \mathbb{C}^N$, the DFT of $z$ is given for every $k\in [0,N-1]\_\mathbb{N}$ by
$$DFT\_z(k)=\frac{1}{N} \sum\_{j=0}^{N-1} z\_j\, \omega^{-k j}$$ where I have denoted by $\omega$ the $N$-th root of unit. That discrete transform is weel known and studied.


I was wondering if it is also well known and studied the following generalization $$GDFT\_z(k)=\frac{1}{N} \sum\_{j=0}^{N-1} z\_{kj}\, \omega^{-k j},$$ in which $z$ is now an $N\times N$ matrix over $\mathbb{C}$.


[Question] Is it still possible to compute my GDFT in $O(N \log N)$?


Thanks in advance,
Josh



A kind of Discrete Fourier Transform
There is no $O(N \log N)$ algorithm, because your computer will take $N^2$ computations to even read the entries of the matrix $z$. However, you definitely get $O(N^2 \log N)$ since this is the usual DFT done $N$ times and suitably restricted.


