What ( fast ) algorithm for evaluating a nine point DFT could be used?

Question

What ( fast ) algorithm for evaluating a nine point DFT could be used? $$ G={V^{(9)}\over{\sqrt{9}}}g=\begin{bmatrix} &1 &1 &\cdots &1 &1 \\ &z_0 &z_1 &\cdots &z_7 &z_8 \\ &z_0^2 &z_1^2 &\cdots &z_7^2 &z_8^2 \\ &\vdots &\vdots & &\vdots &\vdots \\ &z_0^8 &z_1^8 &\cdots &z_7^8 &z_8^8 \\ \end{bmatrix}\begin{bmatrix} g_0\\ g_1\\ g_2\\ \vdots\\ g_8\\ \end{bmatrix} $$ Where $$ z_k=exp(2\pi i k / 9), \ k=0,1,2,...,8 $$

Answer 1

You can reduce it to 3 blocks of dimension 3 DFT's a la Coley-Tukey. However, it is questionable if at these low dimensions there is really a gain in complexity.