What is the number of FLOPs should be for IFFT and FFT algorithm?

[nhuda]

Hello,
I would like to solve a linear equation

**Cx=b**

where **C** is a circulant square matrix with size n*x*n. By applying the circular convolution theorem, **discrete Fourier Transform** can be used to transform the cyclic convolution into component-wise multiplication written as

$\displaystyle F_n(\textbf{c} \star \textbf{x}) = F_n(\textbf{c})F_n(\textbf{x}) = F_n(\textbf{b})$


so that

$\displaystyle x = F_n^{-1}\bigg[\bigg( \frac{(F_n(\textbf{b}))_v)}{(F_n(\textbf{c}))_v}\bigg)_{v\in\textbf{Z}}\bigg]^T$ .

My question is how many number of FLOPs needed to calculate a vector **x**?

 

[Deleted member 4993]

Hello,
I would like to solve a linear equation

**Cx=b**

where **C** is a circulant square matrix with size n*x*n. By applying the circular convolution theorem, **discrete Fourier Transform** can be used to transform the cyclic convolution into component-wise multiplication written as

$ F_n(\textbf{c} \star \textbf{x}) = F_n(\textbf{c})F_n(\textbf{x}) = F_n(\textbf{b}) $


so that

$x = F_n^{-1}\bigg[\bigg( \frac{(F_n(\textbf{b}))_v)}{(F_n(\textbf{c}))_v}\bigg)_{v\in\textbf{Z}}\bigg]^T$ .

My question is how many number of FLOPs needed to calculate a vector **x**?

Please show us what you have tried and exactly where you are stuck.

Please follow the rules of posting in this forum, as enunciated at:

READ BEFORE POSTING​

Please share your work/thoughts about this problem

 

[nhuda]

Hello,
I would like to solve a linear equation



where C is a circulant square matrix with size nxn. By applying the circular convolution theorem, discrete Fourier Transform can be used to transform the cyclic convolution into component-wise multiplication written as



so that

.

My question is how to count the amount of FLOPs needed to calculate a vector x?

Tags

 

[nhuda]

Hello,

From what I understand, the complexity of FFT is O(N log N). However, in my problem to solve vector x, I have to use Inverse FFT (IFFT) and 2 times FFT which are FFT(b) and FFT(c). Hence, does the complexity of vector x is equal to 3 times O(N log N)?