A circulant matrix $C$ can be represented as
$$C = F^{-1} \mbox{diag}(Fc) \, F$$
When $C$ is multiplied by vector $b$
$$C b = F^{-1} \mbox{diag}(Fc) \, (F b)$$
My question only about procedure. As I understood it, to compute $Cb$:
- Find FFT of $b$.
- Find FFT of $c$
- Compute $\mbox{diag}(Fc)*(Fb)$
- Find IFFT of matrix from the third step.
Am I right?