I am doing matrix inversion of circulant matrix using eigenvalue decomposition method. However, I found that the complexity is high which I know as O(n^3). Then, I found that the complexity can be reduced to O(n log n) using Fourier Transform (FFT) method.

Thus, I would be very happy if someone can explain to me the method how to replace Eigenvalue decomposition method with Fourier Transform (FFT) method in order to do matrix inversion.

Eigenvalue decomposition to compute the inversion of circulant matrix, C:

C^{-1} = F x ((lamda)^{-1}) F^{complex conjugate) where F is the eigenvector and lamda is the eigenvalue.

THus, how does FFT can be used to reduce the complexity of this technique?

Thank you.

Huda