Matrix Interpretation of the FFT Algorithm

DFT は行列積で表せる

$X = W x$

$w_{N} = e^{\frac{2 π i}{N}}$ として,

W = w_{N}^{0} w_{N}^{0} ⋮ w_{N}^{0} w_{N}^{1} w_{N}^{1} w_{N}^{N - 1} \dots \dots \dots w_{N}^{0} w_{N}^{N - 1} w_{N}^{(N - 1)^{2}}

Quartz 5