I am currently reading a paper Low Communication FMM-Accelerated FFT on GPUs

In that I am not able to understand the definition of the twiddle factor matrix $T_{P, M}$.

The Fourier matrix $F_N$ is defined as:

$[F_N]_{i, j} = \omega_N^{ij}$

According to the paper, the Fourier matrix is factorised as :

$ F_N = \Pi_{M, P}(I_M \otimes F_P) \Pi_{P, M} T_{P, M} (I_P \otimes F_M) \Pi_{M, P} $

Where $\Pi$ is the block to cyclic operator.

The paper defines $T_{P,M}$ as the diagonal matrix of the twiddle factors.


$[T_{P, M}]_{i, j} = \delta_{i, j} \omega_{N}^{(i\mod M) \cdot \lfloor i/M \rfloor} $

I feel that the above equation is wrong. Because if the matrix is diagonal, then $i < min(P, M)$ meaning that $\lfloor i/M \rfloor$ will always be 0. This would mean that the $T$ is a diagonal matrix of 1s only.

Can someone help me figure out the correct equation for $T$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.