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$:

  1. Find FFT of $b$.
  2. Find FFT of $c$
  3. Compute $\mbox{diag}(Fc)*(Fb)$
  4. Find IFFT of matrix from the third step.

Am I right?

  • $\begingroup$ @RodrigodeAzevedo i am sorry,my bad,mixed up. I am already fixed it. So, what are you think about my question? $\endgroup$ – Аделина Артуровна May 4 at 10:12
  • $\begingroup$ This is confusing. What are the inputs and outputs? $\endgroup$ – Rodrigo de Azevedo May 4 at 10:50
  • $\begingroup$ @RodrigodeAzevedo this is process of computing circulant matrix - vector multiplication O(nlogn) . input- circulant matrix and vector , output- vector. whats wrong? sorry for my english :) $\endgroup$ – Аделина Артуровна May 4 at 13:19
  • $\begingroup$ If $F$ is a Fourier matrix, it does not need to be inverted. That is the whole point. $\endgroup$ – Rodrigo de Azevedo May 4 at 16:50
  • $\begingroup$ @RodrigodeAzevedo . b-input vector. c-first row of C $\endgroup$ – Аделина Артуровна May 4 at 20:49

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.